{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Solve the Equation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: solveEquation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #求解方程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>求解一个给定的方程，将<code>x</code>以字符串 <code>\"x=#value\"</code>&nbsp;的形式返回。该方程仅包含 <code>'+'</code> ， <code>'-'</code> 操作，变量&nbsp;<code>x</code>&nbsp;和其对应系数。</p>\n",
    "\n",
    "<p>如果方程没有解或存在的解不为整数，请返回&nbsp;<code>\"No solution\"</code>&nbsp;。如果方程有无限解，则返回 <code>“Infinite solutions”</code> 。</p>\n",
    "\n",
    "<p>题目保证，如果方程中只有一个解，则 <font color=\"#c7254e\"><font face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size:12.6px\"><span style=\"background-color:#f9f2f4\">'x'</span></span></font></font> 的值是一个整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> equation = \"x+5-3+x=6+x-2\"\n",
    "<strong>输出:</strong> \"x=2\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> equation = \"x=x\"\n",
    "<strong>输出:</strong> \"Infinite solutions\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> equation = \"2x=x\"\n",
    "<strong>输出:</strong> \"x=0\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= equation.length &lt;= 1000</code></li>\n",
    "\t<li><code>equation</code>&nbsp;只有一个&nbsp;<code>'='</code>.&nbsp;</li>\n",
    "\t<li>方程由绝对值在&nbsp;<code>[0, 100]</code>&nbsp; 范围内且无任何前导零的整数和变量 <code>'x'</code>&nbsp;组成。<span style=\"display:block\"><span style=\"height:0px\"><span style=\"position:absolute\">​​​</span></span></span></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [solve-the-equation](https://leetcode.cn/problems/solve-the-equation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [solve-the-equation](https://leetcode.cn/problems/solve-the-equation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"x+5-3+x=6+x-2\"', '\"x=x\"', '\"2x=x\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        def check(st):\n",
    "            a = b = i = 0\n",
    "            m = len(st)\n",
    "            while i<m:\n",
    "                cur = st[i]\n",
    "                while i+1 < m and st[i+1] not in \"+-\":\n",
    "                    cur += st[i+1]\n",
    "                    i+=1\n",
    "                if cur[-1] == \"x\":\n",
    "                    cur = cur[:-1]\n",
    "                    a += int(cur) if cur and cur not in \"+-\" else int(cur+\"1\")\n",
    "                else:\n",
    "                    b += int(cur)\n",
    "                i+=1\n",
    "            return [a,b]\n",
    "        lst = equation.split(\"=\")\n",
    "        a1, b1 = check(lst[0])\n",
    "        a2, b2 = check(lst[1])\n",
    "        if a1 == a2:\n",
    "            return \"Infinite solutions\" if b1==b2 else \"No solution\"\n",
    "        ans = (b2-b1) // (a1-a2)\n",
    "        return f\"x={ans}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        left_num, right_num = 0, 0\n",
    "        left_x, right_x = 0, 0\n",
    "        sign = 1\n",
    "        temp_str = ''\n",
    "        equ_left = True\n",
    "        for i, ch in enumerate(equation):\n",
    "\n",
    "            if ch.isdigit():\n",
    "                temp_str += ch \n",
    "            elif ch == 'x':\n",
    "                if temp_str == '': temp_str = '1'\n",
    "\n",
    "                if equ_left:\n",
    "                    left_x = left_x + sign * int(temp_str)\n",
    "                else:\n",
    "                    right_x = right_x + sign * int(temp_str)\n",
    "\n",
    "                temp_str = ''\n",
    "                sign = 1\n",
    "            elif ch in ('+', '-', '='):\n",
    "                if temp_str != '': \n",
    "                    if equ_left:\n",
    "                        left_num = left_num + sign * int(temp_str)\n",
    "                    else:\n",
    "                        right_num = right_num + sign * int(temp_str)\n",
    "\n",
    "                temp_str = ''\n",
    "                if ch == '+': sign = 1\n",
    "                elif ch == '-': sign = -1\n",
    "\n",
    "            if (i == len(equation) - 1 or ch == '=') and temp_str != '':\n",
    "                if equ_left:\n",
    "                    left_num = left_num + sign * int(temp_str)\n",
    "                else:\n",
    "                    right_num = right_num + sign * int(temp_str)\n",
    "                temp_str = ''\n",
    "                sign = 1\n",
    "\n",
    "            if ch == '=':\n",
    "                equ_left = False\n",
    "                sign = 1\n",
    "\n",
    "            # print(ch, left_num, left_x, left_num, right_x,right_num)\n",
    "\n",
    "        if left_x == right_x and left_num == right_num: return \"Infinite solutions\"\n",
    "        if left_x == right_x and left_num != right_num: return \"No solution\"\n",
    "        # print(left_num, right_num, left_x, right_x)\n",
    "        ans = (right_num - left_num) // (left_x - right_x)\n",
    "        return 'x={}'.format(str(ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        left,right=equation.split(\"=\")\n",
    "        if left==right:\n",
    "            return  \"Infinite solutions\"\n",
    "        start=0\n",
    "        listx=[]\n",
    "        listn=[]\n",
    "        for i in range(len(left)):\n",
    "            if left[i]==\"x\":\n",
    "                start=i+1\n",
    "                end=i\n",
    "                if i == 0:\n",
    "                    listx.append(1)\n",
    "                elif left[i-1]==\"+\"or left[i-1]==\"-\":\n",
    "                    if left[i-1]==\"+\":\n",
    "                        listx.append(1)\n",
    "                    elif left[i-1]==\"-\":\n",
    "                        listx.append(-1)\n",
    "\n",
    "                else:\n",
    "                    while (left[end]!=\"-\" and left[end]!=\"+\") :\n",
    "                        end-=1\n",
    "                        if end<0:\n",
    "                            break\n",
    "\n",
    "                    end=end+1\n",
    "                    if end <=0:\n",
    "                        listx.append(int(left[0:i]))\n",
    "                    elif left[end-1]==\"-\":\n",
    "                        listx.append(-int(left[end:i]))\n",
    "                    elif left[end-1]==\"+\":\n",
    "                        listx.append(int(left[end:i]))\n",
    "\n",
    "\n",
    "            if left[i]==\"+\"or left[i]==\"-\":\n",
    "                if left[start:i]!=\"\":\n",
    "                    listn.append(-int(left[start:i]))\n",
    "                    start=i\n",
    "        if left[-1]!=\"x\":\n",
    "            listn.append(-int(left[start:]))\n",
    "\n",
    "        start=0\n",
    "        for i in range(len(right)):\n",
    "            if right[i]==\"x\":\n",
    "                start=i+1\n",
    "                end=i\n",
    "                if i == 0:\n",
    "                    listx.append(-1)\n",
    "                elif right[i-1]==\"+\"or  right[i-1]==\"-\":\n",
    "                    if right[i-1]==\"+\":\n",
    "                        listx.append(-1)\n",
    "                    elif right[i-1]==\"-\":\n",
    "                        listx.append(1)\n",
    "                else:\n",
    "                    while (right[end]!=\"-\" and right[end]!=\"+\") :\n",
    "                        end-=1\n",
    "                        if end<0:\n",
    "                            break\n",
    "                    end=end+1\n",
    "                    if end <=0:\n",
    "                        listx.append(-int(right[0:i]))\n",
    "                    elif right[end-1]==\"-\":\n",
    "                        listx.append(int(right[end:i]))\n",
    "                    elif right[end-1]==\"+\":\n",
    "                        listx.append(-int(right[end:i]))\n",
    "\n",
    "            if right[i]==\"+\"or right[i]==\"-\":\n",
    "                if right[start:i]!=\"\":\n",
    "                    listn.append(int(right[start:i]))\n",
    "\n",
    "                    start=i\n",
    "        if right[-1]!=\"x\":\n",
    "            listn.append(int(right[start:]))\n",
    "\n",
    "        sumx=sum(listx)\n",
    "        sumn=sum(listn)\n",
    "        if sumx==0 and sumn!=0:\n",
    "            return \"No solution\"\n",
    "        elif sumx==0 and sumn==0:\n",
    "            return \"Infinite solutions\"\n",
    "        elif sumn==0:\n",
    "            return \"x=0\"\n",
    "        else:\n",
    "            k=sumn//sumx\n",
    "            return \"x=\"+str(k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        n = len(equation)\n",
    "        i = 0\n",
    "        sign = 1\n",
    "        factor,val = 0,0\n",
    "        while i < n:\n",
    "            if equation[i] == \"=\":\n",
    "                sign = -1\n",
    "                i += 1\n",
    "                continue\n",
    "            s = sign\n",
    "            if equation[i] == \"+\":\n",
    "                i += 1\n",
    "            if equation[i] == \"-\":\n",
    "                s *= -1\n",
    "                i += 1\n",
    " \n",
    "\n",
    "            value = False\n",
    "            num = 0\n",
    "            while i < n and equation[i].isdigit():\n",
    "                value = True\n",
    "                num = num*10 + int(equation[i])\n",
    "                i += 1 \n",
    "\n",
    "            if i < n and equation[i] == \"x\":\n",
    "                factor += num*s if value else s \n",
    "                i += 1\n",
    "            else:\n",
    "                val += num*s \n",
    "        \n",
    "        if factor == 0 and val == 0:\n",
    "            return \"Infinite solutions\"\n",
    "        if factor == 0 and val != 0:\n",
    "            return \"No solution\"\n",
    "        print(factor)\n",
    "        print(val)\n",
    "        return f\"x={-val//factor}\" \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        def f(e):\n",
    "            e += '+'\n",
    "            sign = 1\n",
    "            c,x = 0,0\n",
    "            seg = ''\n",
    "            for ch in e:\n",
    "                if ch not in '+-':\n",
    "                    seg += ch\n",
    "                else:\n",
    "                    if 'x' in seg:\n",
    "                        if len(seg) == 1:\n",
    "                            x += sign\n",
    "                        else:\n",
    "                            x += sign * int(seg[:-1])\n",
    "                    elif len(seg) > 0:\n",
    "                        c += sign * int(seg)\n",
    "\n",
    "                    seg = ''\n",
    "                    sign = 1 if ch == '+' else -1\n",
    "\n",
    "            return c,x\n",
    "\n",
    "        left, right = equation.split('=')\n",
    "        c1,x1 = f(left)\n",
    "        c2,x2 = f(right)\n",
    "\n",
    "        if c1 == c2 and x1 == x2:\n",
    "            return \"Infinite solutions\"\n",
    "        elif x1 == x2 or (c2-c1)%(x1-x2) != 0:\n",
    "            return \"No solution\"\n",
    "        else:\n",
    "            return 'x=' + str((c2-c1)//(x1-x2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        left, right = '', ''\n",
    "        i = 0\n",
    "        while equation[i] != '=':\n",
    "            left += equation[i]\n",
    "            i += 1\n",
    "        right = equation[i + 1:]\n",
    "    \n",
    "        left_total, left_var = self.calculate(left)\n",
    "        right_total, right_var = self.calculate(right)\n",
    "        if left_var == right_var:\n",
    "            if left_total == right_total:\n",
    "                return \"Infinite solutions\"\n",
    "            else:\n",
    "                return \"No solution\"\n",
    "        diff_var = left_var - right_var\n",
    "        diff_total = right_total - left_total\n",
    "        if diff_total % diff_var == 0:\n",
    "            return \"x={}\".format(diff_total // diff_var)\n",
    "        return \"No solution\"\n",
    "\n",
    "    def calculate(self, string):\n",
    "        total, num_signs = 0, 0\n",
    "        i = 0\n",
    "        while i < len(string):\n",
    "            sign, tmp = '', ''\n",
    "            if string[i] in ['+', '-']:\n",
    "                sign = string[i]\n",
    "                i += 1\n",
    "            while i < len(string) and '0' <= string[i] <= '9':\n",
    "                if not sign:\n",
    "                    sign = '+'\n",
    "                tmp += string[i] \n",
    "                i += 1\n",
    "            if i < len(string) and string[i] == 'x':\n",
    "                if not tmp:\n",
    "                    tmp = '1'\n",
    "                if not sign or sign == '+':\n",
    "                    num_signs += int(tmp)\n",
    "                else:\n",
    "                    num_signs -= int(tmp)\n",
    "                i += 1\n",
    "                continue\n",
    "            total += eval(sign + tmp)\n",
    "        return total, num_signs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        numlst = []\n",
    "        xlst = []\n",
    "\n",
    "\n",
    "        left = equation.split('=')[0].replace('-','+-').split('+')\n",
    "        for i in left:\n",
    "            if i == '':\n",
    "                continue\n",
    "            elif i == '-x':\n",
    "                xlst.append(-1)\n",
    "                continue\n",
    "\n",
    "            if 'x' in i:\n",
    "                xlst.append( int(i.replace('x','')) if i.replace('x','') != '' else 1)\n",
    "            else:\n",
    "                numlst.append(int(i))\n",
    "\n",
    "\n",
    "        right = equation.split('=')[1].replace('-','+-').split('+')\n",
    "        for i in right:\n",
    "            if i == '':\n",
    "                continue\n",
    "            elif i == '-x':\n",
    "                xlst.append(1)\n",
    "                continue\n",
    "\n",
    "            if 'x' in i:\n",
    "                xlst.append(-1*int(i.replace('x','')) if i.replace('x','') != '' else -1)\n",
    "            else:\n",
    "                numlst.append(-1*int(i))\n",
    "        \n",
    "\n",
    "        if sum(numlst) == 0 and sum(xlst) == 0:\n",
    "            return \"Infinite solutions\"\n",
    "        \n",
    "        if sum(numlst) != 0 and sum(xlst) == 0:\n",
    "            return \"No solution\"\n",
    "        \n",
    "        xvalue = -1 * sum(numlst) // sum(xlst)\n",
    "        if xvalue != -1*sum(numlst)/sum(xlst):\n",
    "            return \"No solution\"\n",
    "        return f\"x={str(xvalue)}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "      left, right = equation.split('=')\n",
    "\n",
    "      def cook(x):\n",
    "        x = x.replace('+', ' + ')\n",
    "        x = x.replace('-', ' - ')\n",
    "        x = x.split()\n",
    "        return x\n",
    "\n",
    "      left = cook(left)\n",
    "      right = cook(right)\n",
    "\n",
    "      def calc(x):\n",
    "        cnt = 0\n",
    "        val = 0\n",
    "\n",
    "        def add(y):\n",
    "          nonlocal cnt, val\n",
    "          if y == 'x':\n",
    "            cnt += 1\n",
    "            return\n",
    "          if y.endswith('x'):\n",
    "            cnt += int(y[:-1])\n",
    "            return\n",
    "          val += int(y)\n",
    "\n",
    "        def sub(y):\n",
    "          nonlocal cnt, val\n",
    "          if y == 'x':\n",
    "            cnt -= 1\n",
    "            return\n",
    "          if y.endswith('x'):\n",
    "            cnt -= int(y[:-1])\n",
    "            return\n",
    "          val -= int(y)\n",
    "\n",
    "        i = 0\n",
    "        while i < len(x):\n",
    "          if x[i] == '+':\n",
    "            add(x[i+1])\n",
    "            i += 2\n",
    "            continue\n",
    "          if x[i] == '-':\n",
    "            sub(x[i+1])\n",
    "            i += 2\n",
    "            continue\n",
    "          add(x[i])\n",
    "          i += 1\n",
    "      \n",
    "        return cnt, val\n",
    "      \n",
    "      cnt_left, val_left = calc(left)\n",
    "      cnt_right, val_right = calc(right)\n",
    "\n",
    "      cnt_left -= cnt_right\n",
    "      val_right -= val_left\n",
    "\n",
    "      if cnt_left == 0:\n",
    "        if val_right == 0:\n",
    "          return \"Infinite solutions\"\n",
    "        return \"No solution\"\n",
    "      return \"x=%d\" % (val_right // cnt_left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        factor = 0\n",
    "        val = 0\n",
    "        i = 0\n",
    "        n = len(equation)\n",
    "        sign = 1\n",
    "        while i < n:\n",
    "            if equation[i] == '=':\n",
    "                 sign = -1\n",
    "                 i += 1\n",
    "                 continue\n",
    "            s = sign\n",
    "            if equation[i] == '+':\n",
    "                i += 1\n",
    "            elif equation[i] == '-':\n",
    "                s = -s\n",
    "                i += 1\n",
    "            num = 0\n",
    "            valid = False\n",
    "            while i < n and equation[i].isdigit():\n",
    "                valid = True\n",
    "                num = num * 10 + int(equation[i])\n",
    "                i += 1\n",
    "            if i < n and equation[i] == 'x':\n",
    "                factor += s * num if valid else s\n",
    "                i += 1\n",
    "            else:\n",
    "                val += s * num\n",
    "\n",
    "        if factor == 0:\n",
    "            return 'No solution' if val else 'Infinite solutions'\n",
    "        return f'x={-val // factor}'\n",
    "         \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        a, b, sign = 0, 0, 1\n",
    "        length = len(equation)\n",
    "        index = 0\n",
    "\n",
    "        while index < length:\n",
    "\n",
    "            if equation[index] == \"=\":\n",
    "                sign = sign*(-1)\n",
    "                index += 1\n",
    "\n",
    "                continue\n",
    "\n",
    "            sign_tmp = sign\n",
    "\n",
    "            if equation[index] == \"+\":\n",
    "                index += 1\n",
    "            elif equation[index] == \"-\":\n",
    "                sign_tmp = sign_tmp*(-1)\n",
    "                index += 1\n",
    "            \n",
    "            digit_num, flag = 0, False\n",
    "            while index < length and (\"0\" <= equation[index] <= \"9\"):\n",
    "                digit_num = 10*digit_num + int(equation[index])\n",
    "                index += 1\n",
    "                flag = True\n",
    "\n",
    "            if index < length and equation[index] == \"x\":\n",
    "                if flag:\n",
    "                    a = a + sign_tmp*digit_num\n",
    "                else:\n",
    "                    a = a + sign_tmp\n",
    "                index += 1\n",
    "            else:\n",
    "                b = b + sign_tmp*digit_num\n",
    "\n",
    "        if a == 0:\n",
    "            return \"No solution\" if b else \"Infinite solutions\"\n",
    "\n",
    "        return f\"x={-b//a}\"\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "       # part求解的部分， flag 为1 左边 -1 为右边\n",
    "        def get_part(ans, part, flag):\n",
    "            for part in part.split('+'):\n",
    "                if not part:\n",
    "                    continue\n",
    "                #当前为x项\n",
    "                if part[-1] == 'x':\n",
    "                    #判断当前系数是否1\n",
    "                    if len(part) == 1:\n",
    "                        ans[1] += flag\n",
    "                    elif len(part) == 2 and part[0] == '-':\n",
    "                        ans[1] += -flag \n",
    "                    else:\n",
    "                        ans[1] += int(part[:-1]) * flag\n",
    "                else:\n",
    "                    ans[0] += int(part) * flag\n",
    "        #将-替换为+-\n",
    "        equation = equation.replace(\"-\", \"+-\")\n",
    "        # 将等式分为两部分\n",
    "        left, right = equation.split('=')\n",
    "        # 定义ans ans[0] 为常数项 ans[1] 为1此项\n",
    "        ans = [0, 0]\n",
    "        get_part(ans, left, 1)\n",
    "        get_part(ans, right, -1)\n",
    "\n",
    "        #比较系数项\n",
    "        if ans[1] == 0:\n",
    "            if ans[0] == 0:\n",
    "                return \"Infinite solutions\"\n",
    "            return \"No solution\"      \n",
    "        return f'x={-1*ans[0] // ans[1]}'\n",
    "\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        n = len(equation)\n",
    "        def getXa(s):\n",
    "            # 获取x系数\n",
    "            def help(curS):\n",
    "                if len(curS) == 1:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return int(curS[:-1])\n",
    "            if len(s) == 1:\n",
    "                return help(s)\n",
    "            elif '+' in s:\n",
    "                return help(s[1:])\n",
    "            elif '-' in s:\n",
    "                return -help(s[1:])\n",
    "            else:\n",
    "                return help(s)\n",
    "        def getDigit(s):\n",
    "            a, b = 0, 0\n",
    "            tmpS = s\n",
    "            while tmpS:\n",
    "                plusIdx, minsIdx = float(\"-inf\"), float(\"-inf\")\n",
    "                if '+' in tmpS:\n",
    "                    plusIdx = tmpS.rindex('+')\n",
    "                if '-' in tmpS:\n",
    "                    minsIdx = tmpS.rindex('-')\n",
    "                if plusIdx == minsIdx == float(\"-inf\"):\n",
    "                    if 'x' in tmpS:\n",
    "                        a += getXa(tmpS)\n",
    "                    else:\n",
    "                        b += int(tmpS)\n",
    "                    tmpS = ''\n",
    "                else:\n",
    "                    splitIdx = max(plusIdx, minsIdx)\n",
    "                    curS = tmpS[splitIdx:]\n",
    "                    if 'x' in curS:\n",
    "                        a += getXa(curS)\n",
    "                    else:\n",
    "                        b += int(curS)\n",
    "                    tmpS = tmpS[:splitIdx]\n",
    "            return a, b\n",
    "        leftS, rightS = equation.split('=')\n",
    "        leftA, leftB = getDigit(leftS)\n",
    "        rightA, rightB = getDigit(rightS)\n",
    "\n",
    "        a = leftA - rightA\n",
    "        b = rightB - leftB\n",
    "        if a == 0 and b != 0:\n",
    "            return \"No solution\"\n",
    "        if a == 0 and b == 0:\n",
    "            return \"Infinite solutions\"\n",
    "        return f\"x={int(b // a)}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        sign,cur,num,k,left,has = 1,0,0,0,True,False\n",
    "        for c in equation + \"=\":\n",
    "            if c in \"-+=x\":\n",
    "                if c == \"x\":\n",
    "                    if not has and not cur:\n",
    "                        cur = 1\n",
    "                    k += sign * cur if left else -sign * cur \n",
    "                else:\n",
    "                    num += sign * cur if not left else -sign * cur\n",
    "                cur,has = 0,False\n",
    "            match c:\n",
    "                case \"-\":\n",
    "                    sign = -1\n",
    "                case \"+\":\n",
    "                    sign = 1\n",
    "                case \"=\":\n",
    "                    sign,left = 1, False\n",
    "                case \"x\":\n",
    "                    pass\n",
    "                case _:\n",
    "                    cur, has = cur * 10 + int(c), True \n",
    "        if not k:\n",
    "            return \"No solution\" if num else \"Infinite solutions\"\n",
    "        return f\"x={num//k}\" if not (num % k) else \"No solution\"\n",
    "\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        factor = val = 0\n",
    "        i, n, sign = 0, len(equation), 1  # 等式左边默认系数为正\n",
    "        while i < n:\n",
    "            if equation[i] == '=':\n",
    "                sign = -1\n",
    "                i += 1\n",
    "                continue\n",
    "\n",
    "            s = sign\n",
    "            if equation[i] == '+':  # 去掉前面的符号\n",
    "                i += 1\n",
    "            elif equation[i] == '-':\n",
    "                s = -s\n",
    "                i += 1\n",
    "\n",
    "            num, valid = 0, False\n",
    "            while i < n and equation[i].isdigit():\n",
    "                valid = True\n",
    "                num = num * 10 + int(equation[i])\n",
    "                i += 1\n",
    "\n",
    "            if i < n and equation[i] == 'x':  # 变量\n",
    "                factor += s * num if valid else s\n",
    "                i += 1\n",
    "            else:  # 数值\n",
    "                val += s * num\n",
    "\n",
    "        if factor == 0:\n",
    "            return \"No solution\" if val else \"Infinite solutions\"\n",
    "        return f\"x={-val // factor}\"\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ansys(self, equation):\n",
    "        factor, constant = 0, 0\n",
    "        i = 0\n",
    "        while(i<len(equation)):\n",
    "            if equation[i]=='+':\n",
    "                start = i+1\n",
    "                j = i+1\n",
    "                while(j<len(equation) and equation[j]!='x' and equation[j]!='-' and equation[j]!='+'):\n",
    "                    j+=1\n",
    "                if j<len(equation) and equation[j]=='x':\n",
    "                    if start==j:\n",
    "                        factor += 1\n",
    "                    else:\n",
    "                        factor += int(equation[start: j])\n",
    "                    i = j+1\n",
    "                else:\n",
    "                    constant += int(equation[start: j])\n",
    "                    i=j\n",
    "            else:\n",
    "                start = i+1\n",
    "                j = i+1\n",
    "                while(j<len(equation) and equation[j]!='x' and equation[j]!='-' and equation[j]!='+'):\n",
    "                    j+=1\n",
    "                if j<len(equation) and equation[j]=='x':\n",
    "                    if start==j:\n",
    "                        factor -= 1\n",
    "                    else:\n",
    "                        factor -= int(equation[start: j])\n",
    "                    i = j+1\n",
    "                else:\n",
    "                    constant -= int(equation[start: j])\n",
    "                    i = j\n",
    "        return factor, constant\n",
    "                \n",
    "\n",
    "\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        leftEquation, rightEquation = equation.split('=')[0], equation.split('=')[1]\n",
    "        factor, constant = 0, 0\n",
    "        if leftEquation[0]!='-':\n",
    "            leftEquation = '+'+leftEquation\n",
    "        if rightEquation[0]!='-':\n",
    "            rightEquation = '+'+rightEquation\n",
    "        factorLeft, constantLeft = self.ansys(leftEquation)\n",
    "        factorRight, constantRight = self.ansys(rightEquation)\n",
    "        factor = factorLeft-factorRight\n",
    "        constant = constantRight-constantLeft\n",
    "        if factor==0 and constant!=0: return \"No solution\"\n",
    "        elif factor==0 and constant==0: return \"Infinite solutions\" \n",
    "        else: return \"x=\"+str(int(constant/factor))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def solveEquation(self, equation: str) -> str:\r\n",
    "        lis = [0, 0]\r\n",
    "        flag = False\r\n",
    "        i = 0\r\n",
    "        tmp = ''\r\n",
    "        while(i < len(equation)):\r\n",
    "            if i < len(equation):\r\n",
    "                if equation[i] in ('+', '-'):\r\n",
    "                    tmp = equation[i]\r\n",
    "                    i += 1\r\n",
    "                elif equation[i] == '=':\r\n",
    "                    flag = True\r\n",
    "                    tmp = ''\r\n",
    "                    i += 1\r\n",
    "                    continue\r\n",
    "\r\n",
    "            while(i < len(equation) and equation[i] not in ('+', '-', '=')):\r\n",
    "                tmp += equation[i]\r\n",
    "                i += 1\r\n",
    "            n = len(tmp)\r\n",
    "            ind = 1\r\n",
    "            if 'x' in tmp:\r\n",
    "                tmp = tmp[:n-1]\r\n",
    "                ind = 0\r\n",
    "            if not flag:\r\n",
    "                if tmp == '' or tmp == '+' or tmp == '-':\r\n",
    "                    tmp += '1'\r\n",
    "                lis[ind] += int(tmp)\r\n",
    "            else:\r\n",
    "                if tmp == '' or tmp == '+' or tmp == '-':\r\n",
    "                    tmp += '1'\r\n",
    "                lis[ind] -= int(tmp)\r\n",
    "\r\n",
    "        if lis[0] == 0:\r\n",
    "            if lis[1] == 0:\r\n",
    "                return('Infinite solutions')\r\n",
    "            else:\r\n",
    "                return('No solution')\r\n",
    "        val = -int(lis[1]) // lis[0]\r\n",
    "        return('x={0}'.format(val))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        def lt640(s):\n",
    "            def parse(s):\n",
    "                stack=[]\n",
    "                coef,num=0,0\n",
    "                for ch in s:\n",
    "                    if ch not in ['+','-','x']:\n",
    "                        stack.append(ch)\n",
    "                    elif ch=='x':\n",
    "                        if stack:\n",
    "                            if stack==['+']:coef+=1\n",
    "                            elif stack==['-']:coef-=1\n",
    "                            else:coef+=int(''.join(stack))\n",
    "                            stack=[]\n",
    "                        else:coef+=1\n",
    "                    else:\n",
    "                        if stack:\n",
    "                            num+=int(''.join(stack))\n",
    "                        stack=[ch]\n",
    "                if stack:num+=int(''.join(stack))\n",
    "                return coef,num\n",
    "            s1,s2=s.split('=')\n",
    "            c1,n1=parse(s1)\n",
    "            c2,n2=parse(s2)\n",
    "            coef=c1-c2\n",
    "            num=n2-n1\n",
    "            if coef==0:\n",
    "                if num==0:return 'Infinite solutions'\n",
    "                return 'No solution'\n",
    "            return f'x={num//coef}'\n",
    "        return lt640(equation)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        # 考虑到方程里只有加减，将x=0代入，得到常数项的和；x=1代入，得到常数项+x的个数的和\n",
    "        equ = equation.split('=')\n",
    "        # 这里在前面增添一个+是考虑到以x为开头的情况;替换成*0或者*1是删掉x项或者把系数提出来\n",
    "        left_num = eval(('+'+equ[0]).replace('x','*0').replace('+*','+').replace('-*','-'))\n",
    "        left_x = eval(('+'+equ[0]).replace('x','*1').replace('+*','+').replace('-*','-')) - left_num\n",
    "\n",
    "        right_num = eval(('+'+equ[1]).replace('x','*0').replace('+*','+').replace('-*','-'))\n",
    "        right_x = eval(('+'+equ[1]).replace('x','*1').replace('+*','+').replace('-*','-')) - right_num\n",
    "\n",
    "        if left_x == right_x:\n",
    "            if left_num == right_num:\n",
    "                return 'Infinite solutions'\n",
    "            else:\n",
    "                return 'No solution'\n",
    "        return 'x='+str((right_num - left_num) // (left_x - right_x))\n",
    "        \n",
    "\n",
    "if __name__ == '__main__':\n",
    "    equation = \"x+5-3+x=6+x-2\"\n",
    "    sol = Solution()\n",
    "    print(sol.solveEquation(equation))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        n1 = 0\n",
    "        n = len(equation)\n",
    "        s = equation + '+'\n",
    "        n2 = 0  # 记录x的系数\n",
    "        n3 = 0  # 记录常数\n",
    "        f1 = 1  # 符号位\n",
    "        f2 = 1 \n",
    "        for i in range(n + 1):\n",
    "            if s[i] == '-':\n",
    "                if n1 != 0:\n",
    "                    n3 += f1 * n1 * (-f2)\n",
    "                f1 = -1\n",
    "                n1 = 0\n",
    "            elif s[i] == '+':\n",
    "                if n1 != 0:\n",
    "                    n3 += f1 * n1 * (-f2)\n",
    "                f1 = 1\n",
    "                n1 = 0\n",
    "            elif s[i] == '=':\n",
    "                if n1 != 0:\n",
    "                    n3 += f1 * n1 * (-f2)\n",
    "                f2 = -1\n",
    "                f1 = 1\n",
    "                n1 = 0\n",
    "            elif s[i] == 'x':\n",
    "                if i > 0 and s[i - 1] == '0' and n1 == 0:\n",
    "                    n1 = 0\n",
    "                else:\n",
    "                    n1 = max(n1, 1)\n",
    "                n2 += f1 * f2 * n1\n",
    "                n1 = 0\n",
    "            else:\n",
    "                n1 = n1 * 10 + int(s[i])\n",
    "        print(n2, n3)\n",
    "        if n2 == 0 and n3 == 0:\n",
    "            return 'Infinite solutions'\n",
    "        elif n2 == 0:\n",
    "            return 'No solution'\n",
    "        else:\n",
    "            return f\"x={n3 // n2}\"\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def fc2(string):\n",
    "    lst2 = []\n",
    "    if string[0] not in ['-','+']:\n",
    "        string = '+'+string\n",
    "    idx = string.index('=')\n",
    "    if string[idx+1] not in ['-','+']:\n",
    "        string = string.replace('=','=+')\n",
    "    for s in string:\n",
    "        if s in ['-','+','=']:\n",
    "            lst2.append(s)\n",
    "    # print('string',string)\n",
    "    string = string.replace('=+','_').replace('=-','_').replace('-','_').replace('+','_')\n",
    "    return string.split('_')[1:],lst2\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        lst1,lst2 = fc2(equation)\n",
    "        # print('lst1',lst1)\n",
    "        # print('lst2',lst2)\n",
    "        n = len(lst1)\n",
    "        x_num = 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        i,j=0,0\n",
    "        for _ in range(n):\n",
    "            s = lst1[i]\n",
    "            fh = lst2[j]\n",
    "            if fh=='=':\n",
    "                j+=1\n",
    "                fh = lst2[j]\n",
    "                right = -left\n",
    "            if i==j:\n",
    "                if 'x' in s:\n",
    "                    if len(s)==1:\n",
    "                        s = '1'+s\n",
    "                    x_num = eval('{}{}{}'.format(x_num,fh,s[:-1]))\n",
    "                else:\n",
    "                    left = eval('{}{}{}'.format(left,fh,s))\n",
    "                # print('i=j',x_num,left)\n",
    "            else:\n",
    "                if 'x' in s:\n",
    "                    if len(s)==1:\n",
    "                        s = '1'+s\n",
    "                    x_num = eval('{}-({}{})'.format(x_num,fh,s[:-1]))\n",
    "                else:\n",
    "                    right = eval('{}{}{}'.format(right,fh,s))\n",
    "                # print('i!=j',x_num,right)\n",
    "            i+=1\n",
    "            j+=1\n",
    "        # print('{}x={}'.format(x_num,right))\n",
    "        if x_num==0:\n",
    "            if right==0:\n",
    "                return 'Infinite solutions'\n",
    "            else:\n",
    "                return 'No solution'\n",
    "        elif right%x_num:\n",
    "            return 'No solution'\n",
    "        else:\n",
    "            return 'x={}'.format(right//x_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        n = len(equation)\n",
    "        x = c = i = 0\n",
    "        while i < n:\n",
    "            if equation[i] == \"=\":\n",
    "                x *= -1\n",
    "                c *= -1\n",
    "                i += 1\n",
    "                continue\n",
    "            signal = 1\n",
    "            if equation[i] == \"+\":\n",
    "                i += 1\n",
    "            elif equation[i] == \"-\":\n",
    "                signal = -1\n",
    "                i += 1\n",
    "\n",
    "            num = 0\n",
    "            digit = False\n",
    "            while i < n and equation[i].isdigit():\n",
    "                digit = True\n",
    "                num = num * 10 + int(equation[i])\n",
    "                i += 1\n",
    "            if i<n and equation[i] == \"x\":\n",
    "                x += signal * (num if digit else 1)\n",
    "                i += 1\n",
    "            else:\n",
    "                c += signal * num\n",
    "\n",
    "        if x == 0:\n",
    "            return \"No solution\" if c else \"Infinite solutions\"\n",
    "\n",
    "        return f\"x={-c//x}\"\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "class Solution:\r\n",
    "    def solveEquation(self, equation: str) -> str:\r\n",
    "        # sign: 当前正负, cur: 当前数字, num: 等式的数字项大小, k: 等式x的系数, left: 是否在等号左, has_val: 当前有没有出现任何数字\r\n",
    "        sign, cur, num, k, left, has_val = 1, 0, 0, 0, True, False\r\n",
    "        for c in equation + \"=\":\r\n",
    "            if c in \"-+=x\":\r\n",
    "                if c == 'x':\r\n",
    "                    if not has_val and not cur:\r\n",
    "                        cur = 1\r\n",
    "                    k += sign * cur if left else -sign * cur\r\n",
    "                else:\r\n",
    "                    num += sign * cur if not left else -sign * cur\r\n",
    "                cur, has_val = 0, False\r\n",
    "            match c:\r\n",
    "                case \"-\":\r\n",
    "                    sign = -1\r\n",
    "                case \"+\":\r\n",
    "                    sign = 1\r\n",
    "                case \"=\":\r\n",
    "                    sign, left = 1, False\r\n",
    "                case \"x\":\r\n",
    "                    pass\r\n",
    "                case _:\r\n",
    "                    cur, has_val = cur * 10 + int(c), True\r\n",
    "        if not k:\r\n",
    "            return \"No solution\" if num else \"Infinite solutions\"\r\n",
    "        return f\"x={num//k}\" if not (num % k) else \"No solution\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        equation = equation+'+'\n",
    "        stack = []\n",
    "        re = 1\n",
    "        flag = 1\n",
    "        xcoeff = 0\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for i,ich in enumerate(equation):\n",
    "            if ich.isspace():\n",
    "                continue\n",
    "            if ich.isdigit():\n",
    "                stack.append(eval(ich))\n",
    "                continue\n",
    "            if ich=='+' or ich=='-' or ich=='=':\n",
    "                if len(stack)>0:\n",
    "                    a = stack.pop()\n",
    "                    if a=='x':\n",
    "                        k = 0\n",
    "                        tmpcoef = 0\n",
    "                        if len(stack)==0:\n",
    "                            tmpcoef=1\n",
    "                        while len(stack)>0:\n",
    "                            tmpcoef = tmpcoef+stack.pop()*10**k\n",
    "                            k = k+1\n",
    "                        xcoeff = xcoeff + flag*re*tmpcoef\n",
    "                        \n",
    "                    else:\n",
    "                        tmpr = a\n",
    "                        k = 1\n",
    "                        while len(stack)>0:\n",
    "                            tmpr = tmpr+stack.pop()*10**k\n",
    "                            k = k+1\n",
    " \n",
    "                        res = res+tmpr*flag*re\n",
    "                if ich=='+':\n",
    "                    flag=1\n",
    "                elif ich=='-':\n",
    "                    flag=-1\n",
    "                else:\n",
    "                    flag = 1\n",
    "                    re = -1\n",
    "                continue\n",
    "            if ich == 'x':\n",
    "                stack.append(ich)\n",
    "                continue\n",
    "        if xcoeff == 0 and res==0:\n",
    "            return \"Infinite solutions\"\n",
    "        if xcoeff == 0:\n",
    "            return \"No solution\"\n",
    "        return \"x=\"+str(int(-res/xcoeff))\n",
    "                        \n",
    "                \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef solveEquation(self, eq):\n",
    "\t\ts = eq.split('=')\n",
    "\t\ta = [[0, 0], [0, 0]]\n",
    "\t\tfor i, s in enumerate(eq.split('=')):\n",
    "\t\t\tsign, num = 1, None\n",
    "\t\t\tfor c in s + '+':\n",
    "\t\t\t\tif c in '+-':\n",
    "\t\t\t\t\tif num is not None:\n",
    "\t\t\t\t\t\ta[i][1] += num * sign\n",
    "\t\t\t\t\tsign = 1 if c == '+' else -1\n",
    "\t\t\t\t\tnum = None\n",
    "\t\t\t\telif c == 'x':\n",
    "\t\t\t\t\ta[i][0] += 1 * sign if num is None else num * sign\n",
    "\t\t\t\t\tnum = None\n",
    "\t\t\t\telif c in '0123456789':\n",
    "\t\t\t\t\tnum = (0 if num is None else num) * 10 + int(c)\n",
    "\t\tx, y = a[0][0] - a[1][0], a[1][1] - a[0][1]\n",
    "\t\tif x == 0:\n",
    "\t\t\treturn \"Infinite solutions\" if y == 0 else \"No solution\"\n",
    "\t\telse:\n",
    "\t\t\treturn f\"x={y // x}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        flag = 1\n",
    "        n = len(equation)\n",
    "        num, num_x, num_int, sign = 0, 0, 0, 1\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if equation[i] == '-':\n",
    "                sign = -1\n",
    "                i += 1\n",
    "            elif equation[i] == '+':\n",
    "                sign = 1\n",
    "                i += 1\n",
    "            while i < n and equation[i].isdigit():\n",
    "                num = 10 *num + int(equation[i])\n",
    "                i += 1\n",
    "\n",
    "            if i == n or equation[i] != 'x':\n",
    "                num_int += flag * num * sign\n",
    "                num = 0\n",
    "            else:\n",
    "                if num == 0 and equation[i-1] != '0' or i == 0:\n",
    "                    num = 1 \n",
    "                num_x += flag * num * sign\n",
    "                num = 0\n",
    "                i += 1\n",
    "            \n",
    "            if i < n and equation[i] == '=':\n",
    "                flag = -1\n",
    "                sign = 1\n",
    "                i += 1\n",
    "                \n",
    "        if num_x == 0 and num_int != 0:\n",
    "            return \"No solution\"\n",
    "        elif num_x == 0:\n",
    "            return \"Infinite solutions\"\n",
    "\n",
    "        return f'x={int(-num_int/ num_x)}'\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        sign = 1 \n",
    "        left_x_coefficient = 0\n",
    "        right_constant = 0\n",
    "        equation_length = len(equation)\n",
    "        index = 0 \n",
    "        temp_sign = 1\n",
    "        while index < equation_length:\n",
    "            if equation[index] == '=':\n",
    "                sign *= -1\n",
    "                index += 1\n",
    "            elif equation[index] == '+':\n",
    "                index += 1\n",
    "            elif equation[index] == '-':\n",
    "                temp_sign = -1\n",
    "                index += 1\n",
    "            elif equation[index] == 'x':\n",
    "                left_x_coefficient += (temp_sign * sign) \n",
    "                index += 1 \n",
    "                temp_sign = 1\n",
    "            else:\n",
    "                end_index = index + 1\n",
    "                while end_index < equation_length:\n",
    "                    if equation[end_index] != '+' and equation[end_index] != '-' and equation[end_index] != '=':\n",
    "                        end_index += 1\n",
    "                    else:\n",
    "                        break \n",
    "                if equation[index:end_index].isdigit():\n",
    "                    right_constant += (1 * temp_sign) * (-1 * sign) * (int(equation[index:end_index]))\n",
    "                else:\n",
    "                    left_x_coefficient += temp_sign * sign * (int(equation[index:end_index - 1]))\n",
    "                index = end_index\n",
    "                temp_sign = 1\n",
    "        if left_x_coefficient:\n",
    "            return 'x=' + str(right_constant // left_x_coefficient)\n",
    "        else:\n",
    "            if right_constant:\n",
    "                return 'No solution'\n",
    "            else:\n",
    "                return 'Infinite solutions'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        n = len(equation)\n",
    "        a, b = 0, 0\n",
    "        i, sign = 0, 1\n",
    "        while i < n:\n",
    "            if equation[i] == '=':\n",
    "                sign = -1\n",
    "                i += 1\n",
    "                continue\n",
    "            \n",
    "            s = sign\n",
    "            if equation[i] == '+':\n",
    "                i += 1\n",
    "            elif equation[i] == '-':\n",
    "                s = -s\n",
    "                i += 1\n",
    "            \n",
    "            num, valid = 0, False\n",
    "            while i < n and equation[i].isdigit():\n",
    "                valid = True\n",
    "                num = num * 10 + int(equation[i])\n",
    "                i += 1\n",
    "            if i < n and equation[i] == 'x':\n",
    "                a += s * num if valid else s\n",
    "                i += 1\n",
    "            else:\n",
    "                b += s * num\n",
    "        if a == 0: \n",
    "            return \"No solution\" if b else \"Infinite solutions\"\n",
    "            \n",
    "        return f\"x={-b // a}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        # sign: 当前正负, cur: 当前数字, num: 等式的数字项大小, k: 等式x的系数, left: 是否在等号左, has_val: 当前有没有出现任何数字\n",
    "        sign, cur, num, k, left, has_val = 1, 0, 0, 0, True, False\n",
    "        for c in equation + \"=\":\n",
    "            if c in \"-+=x\":\n",
    "                if c == 'x':\n",
    "                    if not has_val and not cur:\n",
    "                        cur = 1\n",
    "                    k += sign * cur if left else -sign * cur\n",
    "                else:\n",
    "                    num += sign * cur if not left else -sign * cur\n",
    "                cur, has_val = 0, False\n",
    "            match c:\n",
    "                case \"-\":\n",
    "                    sign = -1\n",
    "                case \"+\":\n",
    "                    sign = 1\n",
    "                case \"=\":\n",
    "                    sign, left = 1, False\n",
    "                case \"x\":\n",
    "                    pass\n",
    "                case _:\n",
    "                    cur, has_val = cur * 10 + int(c), True\n",
    "        if not k:\n",
    "            return \"No solution\" if num else \"Infinite solutions\"\n",
    "        return f\"x={num//k}\" if not (num % k) else \"No solution\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str: \n",
    "        lx = []\n",
    "        lnum = []\n",
    "        rx = []\n",
    "        rnum = []\n",
    "        num = [str(i) for i in range(10)]\n",
    "        tmpnum = -1\n",
    "        pos = 1\n",
    "        lflag = 0\n",
    "        xflag = 0\n",
    "        for i in equation:\n",
    "            if not lflag:\n",
    "                if i in num:\n",
    "                    if tmpnum == -1:\n",
    "                        tmpnum = int(i)\n",
    "                    else: \n",
    "                        tmpnum = tmpnum * 10 + int(i)\n",
    "                elif i == 'x':\n",
    "                    xflag = 1\n",
    "                elif i == '+':\n",
    "                    if xflag:\n",
    "                        if tmpnum != -1:\n",
    "                            lx.append(tmpnum * pos)\n",
    "                        else:\n",
    "                            lx.append(1 * pos)\n",
    "                    elif tmpnum != -1:\n",
    "                        lnum.append(tmpnum * pos)\n",
    "                    tmpnum = -1\n",
    "                    xflag = 0\n",
    "                    pos = 1\n",
    "                elif i == '-':\n",
    "                    if xflag:\n",
    "                        if tmpnum != -1:\n",
    "                            lx.append(tmpnum * pos)\n",
    "                        else:\n",
    "                            lx.append(1 * pos)\n",
    "                    elif tmpnum != -1:\n",
    "                        lnum.append(tmpnum * pos)\n",
    "                    tmpnum = -1\n",
    "                    xflag = 0\n",
    "                    pos = -1\n",
    "                elif i == '=':\n",
    "                    lflag = 1\n",
    "                    if xflag:\n",
    "                        if tmpnum != -1:\n",
    "                            lx.append(tmpnum * pos)\n",
    "                        else:\n",
    "                            lx.append(1 * pos)\n",
    "                    elif tmpnum != -1:\n",
    "                        lnum.append(tmpnum * pos)\n",
    "                    tmpnum = -1\n",
    "                    xflag = 0\n",
    "                    pos = 1\n",
    "            elif lflag:\n",
    "                if i in num:\n",
    "                    if tmpnum == -1:\n",
    "                        tmpnum = int(i)\n",
    "                    else: \n",
    "                        tmpnum = tmpnum * 10 + int(i)\n",
    "                elif i == 'x':\n",
    "                    xflag = 1\n",
    "                elif i == '+':\n",
    "                    if xflag:\n",
    "                        if tmpnum != -1:\n",
    "                            rx.append(tmpnum * pos)\n",
    "                        else:\n",
    "                            rx.append(1 * pos)\n",
    "                    elif tmpnum != -1:\n",
    "                        rnum.append(tmpnum * pos)\n",
    "                    tmpnum = -1\n",
    "                    xflag = 0\n",
    "                    pos = 1\n",
    "                elif i == '-':\n",
    "                    if xflag:\n",
    "                        if tmpnum != -1:\n",
    "                            rx.append(tmpnum * pos)\n",
    "                        else:\n",
    "                            rx.append(1 * pos)\n",
    "                    elif tmpnum != -1:\n",
    "                        rnum.append(tmpnum * pos)\n",
    "                    tmpnum = -1\n",
    "                    xflag = 0\n",
    "                    pos = -1\n",
    "        if xflag:\n",
    "            if tmpnum != -1:\n",
    "                rx.append(tmpnum * pos)\n",
    "            else:\n",
    "                rx.append(1 * pos)\n",
    "        elif tmpnum != -1:\n",
    "            rnum.append(tmpnum * pos)    \n",
    "            \n",
    "        print(lx, lnum, rx, rnum)\n",
    "        x = sum(lx) - sum(rx)\n",
    "        n = sum(rnum) - sum(lnum)\n",
    "        if x == 0 and n == 0:\n",
    "            return \"Infinite solutions\"\n",
    "        elif x == 0 and n != 0:\n",
    "            return \"No solution\"\n",
    "        else:\n",
    "            return \"x=\" + str(n//x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        factor = val = 0\n",
    "        i, n, sign = 0, len(equation), 1  # 等式左边默认系数为正\n",
    "        while i < n:\n",
    "            if equation[i] == '=':\n",
    "                sign = -1\n",
    "                i += 1\n",
    "                continue\n",
    "\n",
    "            s = sign\n",
    "            if equation[i] == '+':  # 去掉前面的符号\n",
    "                i += 1\n",
    "            elif equation[i] == '-':\n",
    "                s = -s\n",
    "                i += 1\n",
    "\n",
    "            num, valid = 0, False\n",
    "            while i < n and equation[i].isdigit():\n",
    "                valid = True\n",
    "                num = num * 10 + int(equation[i])\n",
    "                i += 1\n",
    "\n",
    "            if i < n and equation[i] == 'x':  # 变量\n",
    "                factor += s * num if valid else s\n",
    "                i += 1\n",
    "            else:  # 数值\n",
    "                val += s * num\n",
    "\n",
    "        if factor == 0:\n",
    "            return \"No solution\" if val else \"Infinite solutions\"\n",
    "        return f\"x={-val // factor}\"\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        #Lcheck=0\n",
    "        #Rcheck=0\n",
    "        counta=0\n",
    "        countb=0\n",
    "        numbera=0\n",
    "        numberb=0\n",
    "        equation2=equation.split('=')\n",
    "        \n",
    "        first=equation2[0]\n",
    "        second=equation2[1]\n",
    "\n",
    "        if first[0]!='-':\n",
    "            first='+'+first\n",
    "        if second[0]!='-':\n",
    "            second='+'+second\n",
    "        \n",
    "        signalA=[]\n",
    "        contentA=[]\n",
    "        signalB=[]\n",
    "        contentB=[]\n",
    "\n",
    "        temp=''\n",
    "        for i,j in enumerate(first):\n",
    "            if j=='+' or j=='-':\n",
    "                signalA.append(j)\n",
    "                contentA.append(temp)\n",
    "                temp=''\n",
    "            else:\n",
    "                temp+=j\n",
    "                \n",
    "            \n",
    "            if i==len(first)-1:\n",
    "                contentA.append(temp)\n",
    "        \n",
    "        for i,j in enumerate(second):\n",
    "            if j=='+' or j=='-' :\n",
    "                signalB.append(j)\n",
    "                contentB.append(temp)\n",
    "                temp=''\n",
    "            else:\n",
    "                temp+=j\n",
    "                \n",
    "            \n",
    "            if i==len(second)-1:\n",
    "                contentB.append(temp)\n",
    "        \n",
    "        \n",
    "        contentA.pop(0)\n",
    "        contentB.pop(0)\n",
    "        #return contentA\n",
    "        for i in range(len(contentA)):\n",
    "            if signalA[i]=='+':\n",
    "                if 'x' not in contentA[i]:\n",
    "                    numbera+=int(contentA[i])\n",
    "                    #Lcheck=1\n",
    "                else:\n",
    "                    if len(contentA[i])==1:\n",
    "                        counta+=1\n",
    "                    else:\n",
    "                        zz=contentA[i][:-1]\n",
    "                        counta+=int(zz)\n",
    "            else:\n",
    "                if 'x' not in contentA[i]:\n",
    "                    numbera-=int(contentA[i])\n",
    "                    #Lcheck=1\n",
    "                else:\n",
    "                    if len(contentA[i])==1:\n",
    "                        counta-=1\n",
    "                    else:\n",
    "                        zz=contentA[i][:-1]\n",
    "                        counta-=int(zz)\n",
    "        \n",
    "        for i in range(len(contentB)):\n",
    "            if signalB[i]=='+':\n",
    "                if 'x' not in contentB[i]:\n",
    "                    numberb+=int(contentB[i])\n",
    "                    #Rcheck=1\n",
    "                else:\n",
    "                    if len(contentB[i])==1:\n",
    "                        countb+=1\n",
    "                    else:\n",
    "                        zz=contentB[i][:-1]\n",
    "                        countb+=int(zz)\n",
    "            else:\n",
    "                if 'x' not in contentB[i]:\n",
    "                    numberb-=int(contentB[i])\n",
    "                    #Rcheck=1\n",
    "                else:\n",
    "                    if len(contentB[i])==1:\n",
    "                        countb-=1\n",
    "                    else:\n",
    "                        zz=contentB[i][:-1]\n",
    "                        countb-=int(zz)\n",
    "        \n",
    "        #if Lcheck==0 and Rcheck==0:\n",
    "        if counta==countb and numbera==numberb:\n",
    "            return 'Infinite solutions'\n",
    "        elif counta!=countb and numberb==numbera : \n",
    "            return 'x=0'      \n",
    "        elif counta==countb and numbera!=numberb:\n",
    "            return 'No solution'\n",
    "        \n",
    "        #return counta,numbera,countb,numberb\n",
    "        numberb-=numbera\n",
    "        counta-=countb\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        ans=str(int(numberb/counta))\n",
    "        return 'x='+ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        l = [0] * 2\n",
    "        r = [0] * 2\n",
    "        a, b = equation.split('=')\n",
    "        i, sign = 0, 1\n",
    "        while i < len(a):\n",
    "            if a[i] == '+' or a[i] == '-':#符号\n",
    "                if a[i] == '-':\n",
    "                    sign = -1\n",
    "                else:\n",
    "                    sign = 1\n",
    "                i += 1\n",
    "            temp = 0\n",
    "            have_temp = 0\n",
    "            while i < len(a) and a[i] != '+' and a[i] != '-' and a[i] != 'x':\n",
    "                temp = temp * 10 + int(a[i])\n",
    "                have_temp = 1\n",
    "                i += 1# 找数字\n",
    "            if i <len(a):\n",
    "                if a[i] == 'x':\n",
    "                    i += 1\n",
    "                    if have_temp == 0:\n",
    "                        temp = 1\n",
    "                    l[0] += temp * sign\n",
    "                else:\n",
    "                    l[1] += temp * sign\n",
    "            else:\n",
    "                l[1] += temp * sign\n",
    "        print(l)\n",
    "        i = 0\n",
    "        sign = 1\n",
    "        while i < len(b):\n",
    "            if b[i] == '+' or b[i] == '-':#符号\n",
    "                if b[i] == '-':\n",
    "                    sign = -1\n",
    "                else:\n",
    "                    sign = 1\n",
    "                i += 1\n",
    "            temp = 0\n",
    "            have_temp = 0\n",
    "            while i < len(b) and b[i] != '+' and b[i] != '-' and b[i] != 'x':\n",
    "                temp = temp * 10 + int(b[i])\n",
    "                have_temp = 1\n",
    "                i += 1# 找数字\n",
    "            if i <len(b):\n",
    "                if b[i] == 'x':\n",
    "                    i += 1\n",
    "                    if have_temp == 0:\n",
    "                        temp = 1\n",
    "                    r[0] += temp * sign\n",
    "                else:\n",
    "                    r[1] += temp * sign\n",
    "            else:\n",
    "                r[1] += temp * sign\n",
    "        print(r)\n",
    "        #No solution: 无解 或 解非整数\n",
    "        res = [0] * 2\n",
    "        res[0] = l[0] - r[0]\n",
    "        res[1] = r[1] - l[1]# 0 为变量 1 为 数字\n",
    "        if res[0] == 0 and res[1] == 0:\n",
    "            return \"Infinite solutions\"\n",
    "        if res[0] != 0 and res[1] != 0:\n",
    "            temp = res[1] / res[0]\n",
    "            if temp % 1 == 0:\n",
    "                return \"x={}\".format(int(temp))\n",
    "            else:\n",
    "                return \"No solution\"\n",
    "        if res[0] != 0 and res[1] == 0:\n",
    "            return \"x=0\"\n",
    "        if res[0] == 0 and res[1] != 0:\n",
    "            return \"No solution\"\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        n = len(equation)\n",
    "        i = 0\n",
    "        sign = 1\n",
    "        factor,val = 0,0\n",
    "        while i < n:\n",
    "            if equation[i] == \"=\":\n",
    "                sign = -1\n",
    "                i += 1\n",
    "                continue\n",
    "            s = sign\n",
    "            if equation[i] == \"+\":\n",
    "                i += 1\n",
    "            if equation[i] == \"-\":\n",
    "                s *= -1\n",
    "                i += 1\n",
    " \n",
    "\n",
    "            value = False\n",
    "            num = 0\n",
    "            while i < n and equation[i].isdigit():\n",
    "                value = True\n",
    "                num = num*10 + int(equation[i])\n",
    "                i += 1 \n",
    "\n",
    "            if i < n and equation[i] == \"x\":\n",
    "                factor += num*s if value else s \n",
    "                i += 1\n",
    "            else:\n",
    "                val += num*s \n",
    "        \n",
    "        if factor == 0 and val == 0:\n",
    "            return \"Infinite solutions\"\n",
    "        if factor == 0 and val != 0:\n",
    "            return \"No solution\"\n",
    "        print(factor)\n",
    "        print(val)\n",
    "        return f\"x={-val//factor}\" \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        equation = equation.replace('-','+-')\n",
    "        strl,strr = equation.split(\"=\")\n",
    "        ll = strl.split(\"+\")\n",
    "        lr = strr.split(\"+\")\n",
    "        cntl = 0\n",
    "        cntlx = 0\n",
    "        cntr = 0\n",
    "        cntrx = 0\n",
    "        for i in ll:\n",
    "            if i.find(\"x\")>=0:\n",
    "                if i==\"x\":\n",
    "                    cntlx+=1\n",
    "                elif i==\"-x\":\n",
    "                    cntlx-=1\n",
    "                else:\n",
    "                    i = i.replace(\"x\",'')\n",
    "                    cntlx+=int(i)\n",
    "            else:\n",
    "                if i!='':\n",
    "                    cntl+=int(i)\n",
    "        for j in lr:\n",
    "            if j.find(\"x\")>=0:\n",
    "                if j==\"x\":\n",
    "                    cntrx+=1\n",
    "                elif j==\"-x\":\n",
    "                    cntrx-=1\n",
    "                else:\n",
    "                    j = j.replace(\"x\",'')\n",
    "                    cntrx+=int(j)\n",
    "            else:\n",
    "                if j!='':\n",
    "                    cntr+=int(j)\n",
    "        print(cntl,cntlx,cntr,cntrx)\n",
    "        if cntlx == cntrx:\n",
    "            if cntl == cntr:\n",
    "                return \"Infinite solutions\"\n",
    "            else:\n",
    "                return \"No solution\"\n",
    "        if cntl ==cntr:\n",
    "            return \"x=0\"\n",
    "        else:\n",
    "            if (cntr-cntl)/(cntlx-cntrx) == int((cntr-cntl)/(cntlx-cntrx)):\n",
    "                return \"x=\"+str(int((cntr-cntl)/(cntlx-cntrx)))\n",
    "            else:\n",
    "                return \"No solution\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        def get_part(ans, part, flag):\n",
    "            for part in part.split('+'):\n",
    "                if not part:\n",
    "                    continue\n",
    "                if part[-1] == 'x':\n",
    "                    if len(part) == 1:\n",
    "                        ans[1] += flag\n",
    "                    elif len(part) == 2 and part[0] == '-':\n",
    "                        ans[1] += -flag\n",
    "                    else:\n",
    "                        ans[1] += flag * int(part[:-1])\n",
    "                else:\n",
    "                    ans[0] += flag * int(part)\n",
    "        equation = equation.replace('-', '+-')\n",
    "        left, right = equation.split('=')\n",
    "        ans = [0, 0]\n",
    "        get_part(ans, left, 1)\n",
    "        get_part(ans, right, -1)\n",
    "        \n",
    "        if ans[1] == 0:\n",
    "            if ans[0] == 0:\n",
    "                return \"Infinite solutions\"\n",
    "            else:\n",
    "                return \"No solution\"\n",
    "        return f\"x={-1*ans[0] // ans[1]}\"\n",
    "        \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        tmp=\"\"\n",
    "        n=len(equation)\n",
    "        sign=1\n",
    "        last=1\n",
    "        stack=[]\n",
    "        xside=0\n",
    "        nside=0\n",
    "        i=0\n",
    "        while i <n:\n",
    "            kk=equation[i]\n",
    "           # if kk==\"=\":\n",
    "             ##   sign=-1\n",
    "              #  i=i+1\n",
    "              #  continue\n",
    "            #print(stack)\n",
    "            if kk in [\"+\",\"-\",\"=\"]:\n",
    "                if len(stack)==0:\n",
    "                    stack=[]\n",
    "                elif stack[-1]==\"x\":\n",
    "                    if len(stack)==1:\n",
    "                        xside=xside+last*sign*1\n",
    "                    else:\n",
    "                        xside=xside+last*sign*int(\"\".join(stack[:-1]))\n",
    "                else:\n",
    "                    #print(stack)\n",
    "                    nside=nside+last*sign*int(\"\".join(stack))\n",
    "                if kk==\"+\":\n",
    "                    last=1\n",
    "                elif kk==\"-\":\n",
    "                    last=-1\n",
    "                elif kk==\"=\":\n",
    "                    sign=-1\n",
    "                    last=1\n",
    "                #print(stack,nside,xside,sign)\n",
    "                stack=[]\n",
    "\n",
    "            else:\n",
    "                stack.append(kk)\n",
    "            i=i+1\n",
    "        \n",
    "        if len(stack)!=0:\n",
    "            if stack[-1]==\"x\":\n",
    "                if len(stack)==1:\n",
    "                    xside=xside+last*sign*1\n",
    "                else:\n",
    "                    xside=xside+last*sign*int(\"\".join(stack[:-1]))\n",
    "            else:\n",
    "                    #print(stack)\n",
    "                nside=nside+last*sign*int(\"\".join(stack))\n",
    "\n",
    "        print(nside,xside)\n",
    "        if xside==0 and nside!=0:\n",
    "            return \"No solution\"\n",
    "        elif  xside==0 and nside==0:\n",
    "            return \"Infinite solutions\"\n",
    "        else:\n",
    "            return \"x=\"+str(-nside//xside)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        equation = equation.split('=')\n",
    "        left, right = equation[0], equation[1]\n",
    "\n",
    "        def convert(s):\n",
    "            k, value = 0, 0\n",
    "            st = 0\n",
    "            n = len(s)\n",
    "            for i in range(n):\n",
    "                if (s[i] == '-' or s[i] == '+') and st != i:\n",
    "                    value += int(s[st:i])\n",
    "                    st = i\n",
    "                elif s[i] == 'x':\n",
    "                    if i > st + 1:\n",
    "                        k += int(s[st:i])\n",
    "                    else:\n",
    "                        if s[st] == '+' or s[st] == 'x':\n",
    "                            k += 1\n",
    "                        elif s[st] == '-':\n",
    "                            k -= 1\n",
    "                        else:\n",
    "                            k += int(s[st])\n",
    "                    st = i + 1\n",
    "            if st < n: value += int(s[st:])\n",
    "            return k, value\n",
    "\n",
    "        l_k, l_value = convert(left)\n",
    "        r_k, r_value = convert(right)\n",
    "        if l_k == r_k:\n",
    "            if l_value == r_value:\n",
    "                return 'Infinite solutions'\n",
    "            else:\n",
    "                return 'No solution'\n",
    "        else:\n",
    "            return f'x={(r_value - l_value) // (l_k - r_k)}'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        res: complex = eval(\n",
    "            (\"0+\" + equation.replace(\"x\", \"j\"))\n",
    "                .replace(\"=\", \"-(\") \n",
    "                .replace(\"+j\", \"+1j\")\n",
    "                .replace(\"-j\", \"-1j\")\n",
    "                .replace(\"(j\", \"(1j\")\n",
    "                + \")\"\n",
    "                \n",
    "        )\n",
    "        if res == 0:\n",
    "            return \"Infinite solutions\"\n",
    "        return f\"x={-int(res.real / res.imag)}\" if res.imag != 0 else \"No solution\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        def check(st):\n",
    "            a = b = i = 0\n",
    "            m = len(st)\n",
    "            while i < m:\n",
    "                cur = st[i]\n",
    "                while i + 1 < m and st[i + 1] not in \"+-\":\n",
    "                    cur += st[i + 1]\n",
    "                    i += 1\n",
    "                # 更新系数\n",
    "                if cur[-1] == \"x\":\n",
    "                    cur = cur[:-1]\n",
    "                    # 注意\"+x\"\\\"-x\"\\\"x\"的特殊情况\n",
    "                    a += int(cur) if cur and cur not in \"+-\" else int(cur + \"1\")\n",
    "                else:\n",
    "                    b += int(cur)\n",
    "                i += 1\n",
    "            return [a, b]\n",
    "\n",
    "        lst = equation.split(\"=\")\n",
    "        a1, b1 = check(lst[0])\n",
    "        a2, b2 = check(lst[1])\n",
    "        if a1 == a2:\n",
    "            return \"Infinite solutions\" if b1 == b2 else \"No solution\"\n",
    "        ans = (b2 - b1) // (a1 - a2)\n",
    "        return f\"x={ans}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        factor = val = 0\n",
    "        i, n, sign = 0, len(equation), 1  # 等式左边默认系数为正\n",
    "        while i < n:\n",
    "            if equation[i] == '=':\n",
    "                sign = -1\n",
    "                i += 1\n",
    "                continue\n",
    "\n",
    "            s = sign\n",
    "            if equation[i] == '+':  # 去掉前面的符号\n",
    "                i += 1\n",
    "            elif equation[i] == '-':\n",
    "                s = -s\n",
    "                i += 1\n",
    "\n",
    "            num, valid = 0, False\n",
    "            while i < n and equation[i].isdigit():\n",
    "                valid = True\n",
    "                num = num * 10 + int(equation[i])\n",
    "                i += 1\n",
    "\n",
    "            if i < n and equation[i] == 'x':  # 变量\n",
    "                factor += s * num if valid else s\n",
    "                i += 1\n",
    "            else:  # 数值\n",
    "                val += s * num\n",
    "\n",
    "        if factor == 0:\n",
    "            return \"No solution\" if val else \"Infinite solutions\"\n",
    "        return f\"x={-val // factor}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        # 分部计算\n",
    "        def get_part(ans, part, flag):\n",
    "            for p in part.split('+'):\n",
    "                print(p)\n",
    "                if not p:\n",
    "                    continue\n",
    "                if p[-1] == 'x':\n",
    "                    if len(p) == 1:\n",
    "                        ans[1] += flag\n",
    "                    elif len(p) == 2 and p[0] == '-':\n",
    "                        ans[1] += -flag\n",
    "                    else:\n",
    "                        ans[1] += flag * int(p[:-1])\n",
    "                else:\n",
    "                    ans[0] += int(p) * flag\n",
    "\n",
    "        #替换- 为 +-\n",
    "        equation = equation.replace('-', '+-')\n",
    "        left, right = equation.split('=')\n",
    "        ans = [0, 0]\n",
    "        get_part(ans, left, 1)\n",
    "        get_part(ans, right, -1)\n",
    "        if ans[1] == 0:\n",
    "            if ans[0] == 0:\n",
    "                return \"Infinite solutions\"\n",
    "            else:\n",
    "                return \"No solution\"\n",
    "        return f'x={-1*ans[0]//ans[1]}'\n",
    "        \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "# sign: 当前正负, cur: 当前数字, num: 等式的数字项大小, k: 等式x的系数, left: 是否在等号左, has_val: 当前有没有出现任何数字\n",
    "        sign, cur, num, k, left, has_val = 1, 0, 0, 0, True, False\n",
    "        for c in equation + \"=\":\n",
    "            if c in \"-+=x\":\n",
    "                if c == 'x':\n",
    "                    if not has_val and not cur:\n",
    "                        cur = 1\n",
    "                    if left:\n",
    "                        k += sign * cur\n",
    "                    else:\n",
    "                        k += -sign * cur\n",
    "                else:\n",
    "                    if not left:\n",
    "                        num += sign * cur\n",
    "                    else:\n",
    "                        num += -sign * cur\n",
    "                cur, has_val = 0, False\n",
    "            match c:\n",
    "                case \"-\":\n",
    "                    sign = -1\n",
    "                case \"+\":\n",
    "                    sign = 1\n",
    "                case \"=\":\n",
    "                    sign = 1\n",
    "                    left = False\n",
    "                case \"x\":\n",
    "                    pass\n",
    "                case _:\n",
    "                    cur = cur * 10 + int(c)\n",
    "                    has_val = True\n",
    "        if not k:\n",
    "            if num:\n",
    "                return \"No solution\"\n",
    "            else:\n",
    "                return \"Infinite solutions\"\n",
    "        if not (num % k):\n",
    "            return f\"x={num//k}\"\n",
    "        else:\n",
    "            return \"No solution\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        left, right = '', ''\n",
    "        i = 0\n",
    "        while equation[i] != '=':\n",
    "            left += equation[i]\n",
    "            i += 1\n",
    "        right = equation[i + 1:]\n",
    "    \n",
    "        left_total, left_var = self.calculate(left)\n",
    "        right_total, right_var = self.calculate(right)\n",
    "        if left_var == right_var:\n",
    "            if left_total == right_total:\n",
    "                return \"Infinite solutions\"\n",
    "            else:\n",
    "                return \"No solution\"\n",
    "        diff_var = left_var - right_var\n",
    "        diff_total = right_total - left_total\n",
    "        if diff_total % diff_var == 0:\n",
    "            return \"x={}\".format(diff_total // diff_var)\n",
    "        return \"No solution\"\n",
    "\n",
    "    def calculate(self, string):\n",
    "        total, num_signs = 0, 0\n",
    "        i = 0\n",
    "        while i < len(string):\n",
    "            sign, tmp = '', ''\n",
    "            if string[i] in ['+', '-']:\n",
    "                sign = string[i]\n",
    "                i += 1\n",
    "            while i < len(string) and '0' <= string[i] <= '9':\n",
    "                if not sign:\n",
    "                    sign = '+'\n",
    "                tmp += string[i] \n",
    "                i += 1\n",
    "            if i < len(string) and string[i] == 'x':\n",
    "                num_signs += self.cal_x(tmp, sign)\n",
    "                i += 1\n",
    "                continue\n",
    "            total += eval(sign + tmp)\n",
    "        return total, num_signs\n",
    "    \n",
    "    def cal_x(self, num, sign):\n",
    "        num_signs = 0\n",
    "        if not num:\n",
    "            num = '1'\n",
    "        if not sign or sign == '+':\n",
    "            num_signs += int(num)\n",
    "        else:\n",
    "            num_signs -= int(num)\n",
    "        return num_signs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        def get_part(ans, part, flag):\n",
    "            for p in part.split('+'):\n",
    "                if not p:\n",
    "                    continue\n",
    "                if p[-1] == 'x':\n",
    "                    if len(p) == 1:\n",
    "                        ans[1] += flag\n",
    "                    elif len(p) == 2 and p[0] == '-':\n",
    "                        ans[1] += -flag\n",
    "                    else:\n",
    "                        ans[1] += int(p[:-1]) * flag\n",
    "                else:\n",
    "                    ans[0] += flag * int(p)\n",
    "        equation = equation.replace('-', '+-')\n",
    "        ans = [0, 0]\n",
    "        left, right = equation.split('=')\n",
    "        get_part(ans, left, 1)\n",
    "        get_part(ans, right, -1)\n",
    "        \n",
    "        if ans[1] == 0:\n",
    "            if ans[0] == 0:\n",
    "                return \"Infinite solutions\"\n",
    "            else:\n",
    "                return \"No solution\"\n",
    "        return f\"x={-ans[0] // ans[1]}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    logs = \"\"\n",
    "\n",
    "    def log(self, s):\n",
    "        self.logs += f'{s}\\n'\n",
    "\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        left_right = [0, 0]\n",
    "        has_eq = 1\n",
    "        tmp_value = 0\n",
    "        is_x = False\n",
    "        last_op = 1\n",
    "        equation = equation.replace('0x', '0')\n",
    "\n",
    "        def hander(value, index):\n",
    "            left_right[index] += value\n",
    "            self.log([value, is_x])\n",
    "        for v in equation:\n",
    "            is_x = 0\n",
    "            if ord('0') <= ord(v) <= ord('9'):\n",
    "                tmp_value = tmp_value*10+int(v)\n",
    "            else:\n",
    "                if v == '=':\n",
    "                    if tmp_value:\n",
    "                        hander(last_op*tmp_value*has_eq, is_x)\n",
    "                        tmp_value = 0\n",
    "                    has_eq = -1\n",
    "                    last_op = 1\n",
    "                    continue\n",
    "                if v == 'x':\n",
    "                    if not tmp_value:\n",
    "                        tmp_value = 1\n",
    "                    is_x = 1\n",
    "                if tmp_value:\n",
    "                    hander(last_op*tmp_value*has_eq, is_x)\n",
    "                    tmp_value = 0\n",
    "                if v == '+':\n",
    "                    last_op = 1\n",
    "                if v == '-':\n",
    "                    last_op = -1\n",
    "\n",
    "        if tmp_value:\n",
    "            hander(last_op*tmp_value*has_eq, is_x)\n",
    "        if left_right[1] == 0:\n",
    "            if left_right[0] == 0:\n",
    "                return 'Infinite solutions'\n",
    "            return \"No solution\"\n",
    "        return f'x={left_right[0]//-left_right[1]}'\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = Solution()\n",
    "    for case in [\n",
    "        [\"x+5-3+x=6+x-2\", \"x=2\"],\n",
    "        [\"2x+3x-6x=x+2\", \"x=-1\"],\n",
    "        [\"x=x+2\", \"No solution\"],\n",
    "        [\"x=x\", \"Infinite solutions\"],\n",
    "        [\"2x=x\", \"x=0\"],\n",
    "        [\"2=-x\", \"x=-2\"],\n",
    "        [\"0x=0\", \"Infinite solutions\"],\n",
    "        [\"1+1=x\", \"x=2\"]\n",
    "    ]:\n",
    "        s.logs = \"\"\n",
    "        e = s.solveEquation(*case[:-1])\n",
    "        if e != case[-1]:\n",
    "            print(e, case)\n",
    "            print(s.logs)\n",
    "            break\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        #左,右子项分割等式项\n",
    "        left, right = equation.split('=')\n",
    "        #定义一个fn函数\n",
    "        def fn(s): \n",
    "            ii = x = y = 0\n",
    "            for i in range(len(s)+1):\n",
    "                #计算常量值\n",
    "                if i == len(s) or s[i] in \"+-\": \n",
    "                    if ii < i: \n",
    "                        y += int(s[ii:i])\n",
    "                        \n",
    "                    ii = i\n",
    "                #计算带有x的值\n",
    "                elif s[i] == \"x\":\n",
    "                    if ii == i or s[ii:i] in \"+-\": \n",
    "                        x += int(s[ii:i] + \"1\")\n",
    "                    else: \n",
    "                        x += int(s[ii:i])\n",
    "                    ii = i+1\n",
    "            return x, y\n",
    "        \n",
    "        (lx, ly), (rx, ry) = fn(left), fn(right)\n",
    "        print(lx,ly)\n",
    "        print(rx,ry)\n",
    "        if lx == rx:\n",
    "            if ly == ry: \n",
    "                return 'Infinite solutions'\n",
    "            else: \n",
    "                return 'No solution'\n",
    "        \n",
    "        return f'x={(ry - ly) // (lx - rx)}'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        n = len(equation)\n",
    "        x = c = i = 0\n",
    "        while i < n:\n",
    "            if equation[i] == \"=\":\n",
    "                x *= -1\n",
    "                c *= -1\n",
    "                i += 1\n",
    "                continue\n",
    "\n",
    "            signal = 1\n",
    "            if equation[i] == \"+\":\n",
    "                i += 1\n",
    "            elif equation[i] == \"-\":\n",
    "                signal = -1\n",
    "                i += 1\n",
    "\n",
    "            num = 0\n",
    "            digit = False\n",
    "            while i < n and equation[i].isdigit():\n",
    "                digit = True\n",
    "                num = num * 10 + int(equation[i])\n",
    "                i += 1\n",
    "                \n",
    "            if i<n and equation[i] == \"x\":\n",
    "                x += signal * (num if digit else 1)\n",
    "                i += 1\n",
    "            else:\n",
    "                c += signal * num\n",
    "\n",
    "        if x == 0:\n",
    "            return \"No solution\" if c else \"Infinite solutions\"\n",
    "\n",
    "        return f\"x={-c//x}\"\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        n = len(equation)\n",
    "        i = 0\n",
    "        xishux = xishuc = 0\n",
    "        sign = 1\n",
    "        while i < n:\n",
    "            if equation[i] == '=':\n",
    "                sign = -1\n",
    "                i += 1\n",
    "                continue\n",
    "\n",
    "            s = sign\n",
    "            if equation[i] == '-':\n",
    "                s = -s\n",
    "                i += 1\n",
    "            elif equation[i] == '+':\n",
    "                i += 1\n",
    "\n",
    "            num = 0\n",
    "            valid = False\n",
    "            while i < n and equation[i].isdigit():\n",
    "                valid = True\n",
    "                num = num * 10 + int(equation[i])\n",
    "                i += 1\n",
    "\n",
    "            if i < n and equation[i] == 'x':\n",
    "                xishux += num * s if valid else 1 * s\n",
    "                i += 1\n",
    "            else:\n",
    "                xishuc += num * s\n",
    "            print(xishuc, xishux)\n",
    "        if xishux == 0:\n",
    "            if xishuc == 0: return 'Infinite solutions'\n",
    "            else: return 'No solution'\n",
    "        \n",
    "        return 'x='+str(-xishuc//xishux)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        k = [0, 0]\n",
    "        b = [0, 0] \n",
    "        sign = [1, 1]\n",
    "        idx = 0  \n",
    "        n = len(equation)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if equation[i] == '+':\n",
    "                i+=1\n",
    "            elif equation[i] == '-':\n",
    "                sign[idx] = -1 * sign[idx]\n",
    "                i+=1\n",
    "            elif equation[i] == '=':\n",
    "                idx += 1\n",
    "                i+=1\n",
    "            elif equation[i].isdigit():\n",
    "                num = 0 \n",
    "                while i < n and equation[i].isdigit():\n",
    "                    num = num * 10 + int(equation[i])\n",
    "                    i+=1\n",
    "                if i < n and equation[i].isalpha():\n",
    "                    k[idx] += sign[idx] * num \n",
    "                    sign[idx]=1\n",
    "                    i+=1\n",
    "                else:\n",
    "                    b[idx] += sign[idx] * num \n",
    "                    sign[idx]=1\n",
    "            elif equation[i].isalpha():\n",
    "                k[idx] += sign[idx]\n",
    "                sign[idx] = 1\n",
    "                i+=1 \n",
    "        k[0] -= k[1]\n",
    "        k[1] = 0\n",
    "        b[1] -= b[0]\n",
    "        b[0] = 0 \n",
    "        if b[1] == 0 and k[0] == 0:\n",
    "            return 'Infinite solutions'\n",
    "        elif k[0] == 0 and b[1] != 0:\n",
    "            return 'No solution'\n",
    "        else:\n",
    "            return 'x={}'.format(b[1]//k[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        def change(s):\n",
    "            i = 0\n",
    "            number = []\n",
    "            fac_coef = []\n",
    "            n = len(s)\n",
    "            while i < n:\n",
    "                flag = 1\n",
    "                if i < n and s[i] == '+':\n",
    "                    i = i+1\n",
    "                if i < n and s[i] == '-':\n",
    "                    flag = -flag\n",
    "                    i = i+1\n",
    "                isnum = False\n",
    "                num = 0\n",
    "                while i < n and s[i].isdigit():        \n",
    "                    isnum = True\n",
    "                    num = num*10 + int(s[i])\n",
    "                    i = i+1\n",
    "                    \n",
    "                if i < n and s[i] == 'x':\n",
    "                    if isnum:\n",
    "                        fac_coef.append(flag*num)\n",
    "                        i = i+1\n",
    "                    else: \n",
    "                        fac_coef.append(flag)\n",
    "                        i = i+1\n",
    "                else:\n",
    "                    if isnum:\n",
    "                        number.append(flag*num)\n",
    "            return sum(number), sum(fac_coef)\n",
    "        equation1 = equation.split('=')\n",
    "        num_left, coef_left = change(equation1[0])\n",
    "        num_right, coef_right = change(equation1[1])\n",
    "        allnum = num_left - num_right\n",
    "        allcoef = coef_left - coef_right\n",
    "\n",
    "        if allcoef==0:\n",
    "            return \"Infinite solutions\" if allnum == 0 else \"No solution\"\n",
    "        return f\"x={(-1)*allnum//allcoef}\" if not (allnum % allcoef) else \"No solution\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        # 1. 等式分为两边 等号左边计入left 右边计入right\n",
    "        # 2. 建立left_num, left_x, right_num, right_x \n",
    "        index = equation.index('=')\n",
    "        num, flag = 0, 1\n",
    "        left_stack, right_stack = [], []\n",
    "        left_x, right_x = 0, 0\n",
    "        x_zero = -1 #标记x前面是否为0\n",
    "        for i in range(index):\n",
    "            if equation[i] == 'x':\n",
    "                if x_zero == 0:\n",
    "                    pass\n",
    "                else:\n",
    "                    left_x += num * flag if num else flag\n",
    "                num = 0\n",
    "            elif equation[i] == '+':\n",
    "                left_stack.append(flag * num)\n",
    "                num, flag = 0, 1\n",
    "            elif equation[i] == '-':\n",
    "                left_stack.append(flag * num)\n",
    "                num, flag = 0 , -1\n",
    "            else:\n",
    "                #数字\n",
    "                num =10 * num + int(equation[i])\n",
    "                x_zero = num   \n",
    "        if num:\n",
    "            left_stack.append(num * flag)\n",
    "        num, flag = 0, 1\n",
    "        x_zero = -1\n",
    "        for j in range(index + 1, len(equation)):\n",
    "            if equation[j] == 'x':\n",
    "                if x_zero == 0:\n",
    "                    pass\n",
    "                else:\n",
    "                    right_x += num * flag if num else flag\n",
    "                num = 0\n",
    "            elif equation[j] == '+':\n",
    "                right_stack.append(flag * num)\n",
    "                num, flag = 0, 1\n",
    "            elif equation[j] == '-':\n",
    "                right_stack.append(flag * num)\n",
    "                num, flag = 0 , -1\n",
    "            else:\n",
    "                #数字\n",
    "                num =10 * num + int(equation[j])\n",
    "                x_zero = num\n",
    "        if num:\n",
    "            right_stack.append(num * flag)\n",
    "\n",
    "        sum_left = sum(left_stack)\n",
    "        sum_right = sum(right_stack)\n",
    "        # print(left_x, right_x)\n",
    "        print(left_stack, right_stack)\n",
    "        if left_x == right_x and sum_left == sum_right:\n",
    "            return \"Infinite solutions\"\n",
    "        elif left_x == right_x and sum_left != sum_right:\n",
    "            return \"No solution\"\n",
    "        else:\n",
    "            return f'x={str((sum_right - sum_left) // (left_x - right_x))}'\n",
    "        # elif left_x > right_x:\n",
    "        #     return \"x=\" + str((sum_right - sum_left) // (left_x - right_x))\n",
    "        # else:\n",
    "        #     return \"x=\" + str((sum_left - sum_right) // (right_x - left_x))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        def evaluate(expression):\n",
    "            sum_x, sum_val = 0, 0\n",
    "            sign, num = 1, \"\"\n",
    "\n",
    "            for ch in expression + '+':\n",
    "                if ch in ['+', '-']:\n",
    "                    if num:\n",
    "                        if 'x' in num:\n",
    "                            coef = num.replace('x', '') or '1'\n",
    "                            sum_x += sign * int(coef)\n",
    "                        else:\n",
    "                            sum_val += sign * int(num)\n",
    "                    num = \"\"\n",
    "                    sign = 1 if ch == '+' else -1\n",
    "                else:\n",
    "                    num += ch\n",
    "            return sum_x, sum_val\n",
    "        \n",
    "        left, right = equation.split('=')\n",
    "        left_x, left_val = evaluate(left)\n",
    "        right_x, right_val = evaluate(right)\n",
    "\n",
    "        coef = left_x - right_x\n",
    "        const = right_val - left_val\n",
    "\n",
    "        if coef == 0:\n",
    "            if const == 0:\n",
    "                return \"Infinite solutions\"\n",
    "            else:\n",
    "                return \"No solution\"\n",
    "        else:\n",
    "            return \"x=\" + str(const // coef)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        # 1. 等式分为两边 等号左边计入left 右边计入right\n",
    "        # 2. 建立left_num, left_x, right_num, right_x \n",
    "        index = equation.index('=')\n",
    "        num, flag = 0, 1\n",
    "        left_stack, right_stack = [], []\n",
    "        left_x, right_x = 0, 0\n",
    "        x_zero = -1\n",
    "        for i in range(index):\n",
    "            if equation[i] == 'x':\n",
    "                if x_zero == 0:\n",
    "                    left_x = 0\n",
    "                else:\n",
    "                    left_x += num * flag if num else flag\n",
    "                num = 0\n",
    "            elif equation[i] == '+':\n",
    "                left_stack.append(flag * num)\n",
    "                num, flag = 0, 1\n",
    "            elif equation[i] == '-':\n",
    "                left_stack.append(flag * num)\n",
    "                num, flag = 0 , -1\n",
    "            else:\n",
    "                #数字\n",
    "                num =10 * num + int(equation[i])\n",
    "                x_zero = num   \n",
    "        if num:\n",
    "            left_stack.append(num * flag)\n",
    "        num, flag = 0, 1\n",
    "        x_zero = -1\n",
    "        for j in range(index + 1, len(equation)):\n",
    "            if equation[j] == 'x':\n",
    "                if x_zero == 0:\n",
    "                    right_x = 0\n",
    "                else:\n",
    "                    right_x += num * flag if num else flag\n",
    "                num = 0\n",
    "            elif equation[j] == '+':\n",
    "                right_stack.append(flag * num)\n",
    "                num, flag = 0, 1\n",
    "            elif equation[j] == '-':\n",
    "                right_stack.append(flag * num)\n",
    "                num, flag = 0 , -1\n",
    "            else:\n",
    "                #数字\n",
    "                num =10 * num + int(equation[j])\n",
    "                x_zero = num\n",
    "        if num:\n",
    "            right_stack.append(num * flag)\n",
    "        sum_left = sum(left_stack)\n",
    "        sum_right = sum(right_stack)\n",
    "        # print(left_x, right_x)\n",
    "        print(left_stack, right_stack)\n",
    "        if left_x == right_x and sum_left == sum_right:\n",
    "            return \"Infinite solutions\"\n",
    "        elif left_x == right_x and sum_left != sum_right:\n",
    "            return \"No solution\"\n",
    "        elif left_x > right_x:\n",
    "            return \"x=\" + str((sum_right - sum_left) // (left_x - right_x))\n",
    "        else:\n",
    "            return \"x=\" + str((sum_left - sum_right) // (right_x - left_x))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        equation = equation.split(\"=\")\n",
    "        left, right = equation[0]+\"+\", equation[1]+\"+\"\n",
    "        l_x = []\n",
    "        l_n = []\n",
    "        r_x = []\n",
    "        r_n = []\n",
    "        p, q = 0, 1\n",
    "        while q<len(left):\n",
    "            if left[q]=='+' or left[q]=='-':\n",
    "                s = left[p:q]\n",
    "                if s[-1]=='x':\n",
    "                    l_x.append(s[:-1])\n",
    "                else:\n",
    "                    l_n.append(s)\n",
    "                p = q\n",
    "            q += 1\n",
    "        p, q = 0, 1\n",
    "        while q<len(right):\n",
    "            if right[q]=='+' or right[q]=='-':\n",
    "                s = right[p:q]\n",
    "                if s[-1]=='x':\n",
    "                    r_x.append(s[:-1])\n",
    "                else:\n",
    "                    r_n.append(s)\n",
    "                p = q\n",
    "            q += 1\n",
    "        sum_n = 0\n",
    "        sum_x = 0\n",
    "        for s in l_n:\n",
    "            sum_n -= int(s)\n",
    "        for s in r_n:\n",
    "            sum_n += int(s)\n",
    "        for s in l_x:\n",
    "            if s=='' or s=='+':\n",
    "                sum_x += 1\n",
    "            elif s=='-':\n",
    "                sum_x += -1\n",
    "            else:\n",
    "                sum_x += int(s)\n",
    "        for s in r_x:\n",
    "            if s=='' or s=='+':\n",
    "                sum_x -= 1\n",
    "            elif s=='-':\n",
    "                sum_x -= -1\n",
    "            else:\n",
    "                sum_x -= int(s)\n",
    "        # print(l_x, sum_n)\n",
    "        if sum_x==0 and sum_n==0:\n",
    "            return \"Infinite solutions\"\n",
    "        if sum_x==0 and sum_n!=0:\n",
    "            return \"No solution\"\n",
    "        else:\n",
    "            return \"x=\"+str(int(sum_n/sum_x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        # factor表示变量系数和，val表示数字和, 本质只需要维护factor和val\n",
    "        factor, val = 0, 0\n",
    "        n = len(equation)\n",
    "        lr_sign, pn_sign = 1, 1 #等式左边默认系数为正\n",
    "        num = 'initial'\n",
    "        for i in range(n):\n",
    "            # 开始模拟\n",
    "            if equation[i] == '=':\n",
    "                if num != 'initial':\n",
    "                    val += num * pn_sign\n",
    "                lr_sign = -1\n",
    "                pn_sign = lr_sign\n",
    "                num = 'initial'\n",
    "            elif equation[i] == 'x':\n",
    "                if num != 'initial':\n",
    "                    factor += pn_sign * num\n",
    "                else:\n",
    "                    factor += pn_sign\n",
    "                num = 'initial'\n",
    "            elif equation[i] == '+':\n",
    "                if num != 'initial':\n",
    "                    val += num * pn_sign\n",
    "                pn_sign = lr_sign\n",
    "                num = 'initial'\n",
    "            elif equation[i] == '-':\n",
    "                if num != 'initial':\n",
    "                    val += num * pn_sign\n",
    "                pn_sign = - lr_sign\n",
    "                num = 'initial'\n",
    "            elif equation[i].isdigit(): # 数\n",
    "                if num != 'initial':\n",
    "                    num = 10 * num + int(equation[i])\n",
    "                else:\n",
    "                    num = int(equation[i])\n",
    "\n",
    "            if i == n-1:\n",
    "                if num != 'initial':\n",
    "                    val += num * pn_sign\n",
    "\n",
    "        if factor == 0:\n",
    "            if val == 0:\n",
    "                ans = \"Infinite solutions\"\n",
    "            else:\n",
    "                ans = \"No solution\"\n",
    "        else:\n",
    "            ans = f\"x={int(-val / factor)}\" if -val/factor == int(-val/factor) else \"No solution\"\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    模拟\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        n = len(equation)\n",
    "        lis = []\n",
    "        prev = 0\n",
    "        for i, ch in enumerate(equation):\n",
    "            if ch != \"+\" and ch != \"-\" and ch != \"=\":\n",
    "                prev += 1\n",
    "            else:\n",
    "                lis.append(equation[i-prev:i])\n",
    "                lis.append(equation[i])\n",
    "                prev = 0\n",
    "        lis.append(equation[n-prev:n])\n",
    "        alpha, beta = 0, 0 \n",
    "        tag = 1   # 是否出现= 1, -1\n",
    "        prev = 1\n",
    "        for s in lis:\n",
    "            if len(s) == 0:\n",
    "                continue\n",
    "            if s[-1] == \"x\":\n",
    "                if len(s) == 1:\n",
    "                    alpha += prev * tag\n",
    "                else:\n",
    "                    alpha += int(s[:-1]) * prev * tag\n",
    "                prev = 1\n",
    "            elif s == \"-\":\n",
    "                prev = -1\n",
    "            elif s == \"=\":\n",
    "                tag = -1\n",
    "            elif s.isdigit():\n",
    "                beta -= int(s) * prev * tag\n",
    "                prev = 1\n",
    "        \n",
    "        if alpha == 0 and beta == 0:\n",
    "            return \"Infinite solutions\"\n",
    "        elif alpha == 0:\n",
    "            return \"No solution\"\n",
    "        return f\"x={beta//alpha}\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        a, b, sign = 0, 0, 1\n",
    "        length = len(equation)\n",
    "        index = 0\n",
    "\n",
    "        while index < length:\n",
    "\n",
    "            if equation[index] == \"=\":\n",
    "                sign = sign*(-1)\n",
    "                index += 1\n",
    "                continue\n",
    "\n",
    "            sign_tmp = sign\n",
    "\n",
    "            if equation[index] == \"+\":\n",
    "                index += 1\n",
    "            elif equation[index] == \"-\":\n",
    "                sign_tmp = sign_tmp*(-1)\n",
    "                index += 1\n",
    "            \n",
    "            digit_num, flag = 0, False\n",
    "            while index < length and (\"0\" <= equation[index] <= \"9\"):\n",
    "                digit_num = 10*digit_num + int(equation[index])\n",
    "                index += 1\n",
    "                flag = True\n",
    "\n",
    "            if index < length and equation[index] == \"x\":\n",
    "                if flag:\n",
    "                    a = a + sign_tmp*digit_num\n",
    "                else:\n",
    "                    a = a + sign_tmp\n",
    "                index += 1\n",
    "            else:\n",
    "                b = b + sign_tmp*digit_num\n",
    "\n",
    "        if a == 0:\n",
    "            return \"No solution\" if b else \"Infinite solutions\"\n",
    "\n",
    "        return f\"x={-b//a}\"\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "         # 1. 等式分为两边 等号左边计入left 右边计入right\n",
    "        # 2. 建立left_num, left_x, right_num, right_x \n",
    "        index = equation.index('=')\n",
    "        def get_res(start, end, flag):\n",
    "            val_sum, val_x, num = 0, 0, 0\n",
    "            x_zero = -1\n",
    "            for i in range(start, end):\n",
    "                if equation[i] == 'x':\n",
    "                    #x系数不为0\n",
    "                    if x_zero != 0:\n",
    "                        val_x += num * flag if num else flag\n",
    "                    num = 0\n",
    "                elif equation[i] == '+':\n",
    "                    val_sum += flag * num\n",
    "                    num, flag = 0, 1\n",
    "                elif equation[i] == '-':\n",
    "                    val_sum += flag * num\n",
    "                    num, flag = 0 , -1\n",
    "                else:\n",
    "                    num =10 * num + int(equation[i])\n",
    "                    x_zero = num # 考虑x系数是否为0\n",
    "            val_sum += flag * num\n",
    "            return val_sum, val_x\n",
    "        sum_left, left_x = get_res(0, index, 1)\n",
    "        sum_right, right_x = get_res(index + 1, len(equation), 1)\n",
    "\n",
    "        if left_x == right_x and sum_left == sum_right:\n",
    "            return \"Infinite solutions\"\n",
    "        elif left_x == right_x and sum_left != sum_right:\n",
    "            return \"No solution\"\n",
    "        else:\n",
    "            return f'x={str((sum_right - sum_left) // (left_x - right_x))}'\n",
    "    \n",
    "                \n",
    "\n",
    "        \n",
    "        \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, q: str) -> str:\n",
    "        right = 1\n",
    "        fuhao = 1\n",
    "        tmp = \"\"\n",
    "        A = B = 0\n",
    "        for s in q:\n",
    "            if s in \"+-=\":\n",
    "                B += fuhao * (int(tmp) if tmp else 0) * right\n",
    "                tmp = \"\"\n",
    "                if s == \"=\":\n",
    "                    right = -1\n",
    "                    fuhao = 1\n",
    "                elif s == \"+\":\n",
    "                    fuhao = 1\n",
    "                elif s == \"-\":\n",
    "                    fuhao = -1\n",
    "            elif s == \"x\":\n",
    "                A += fuhao * (int(tmp) if tmp else 1) * right\n",
    "                tmp = \"\"\n",
    "            else:\n",
    "                tmp += s\n",
    "        if tmp:\n",
    "            B += fuhao * (int(tmp) if tmp else 1) * right\n",
    "        if A == 0:\n",
    "            return \"Infinite solutions\" if B == 0 else \"No solution\"\n",
    "        return \"x=\" + str( -1 * B // A)\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        factor = val = 0\n",
    "        i, n, sign = 0, len(equation), 1  # 等式左边默认系数为正\n",
    "        while i < n:\n",
    "            if equation[i] == '=':\n",
    "                sign = -1\n",
    "                i += 1\n",
    "                continue\n",
    "\n",
    "            s = sign\n",
    "            if equation[i] == '+':  # 去掉前面的符号\n",
    "                i += 1\n",
    "            elif equation[i] == '-':\n",
    "                s = -s\n",
    "                i += 1\n",
    "\n",
    "            num, valid = 0, False\n",
    "            while i < n and equation[i].isdigit():\n",
    "                valid = True\n",
    "                num = num * 10 + int(equation[i])\n",
    "                i += 1\n",
    "\n",
    "            if i < n and equation[i] == 'x':  # 变量\n",
    "                factor += s * num if valid else s\n",
    "                i += 1\n",
    "            else:  # 数值\n",
    "                val += s * num\n",
    "\n",
    "        if factor == 0:\n",
    "            return \"No solution\" if val else \"Infinite solutions\"\n",
    "        return f\"x={-val // factor}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        # 1. 等式分为两边 等号左边计入left 右边计入right\n",
    "        # 2. 建立left_num, left_x, right_num, right_x \n",
    "        index = equation.index('=')\n",
    "        num, flag = 0, 1\n",
    "        left_stack, right_stack = [], []\n",
    "        left_x, right_x = 0, 0\n",
    "        x_zero = -1\n",
    "        for i in range(index):\n",
    "            if equation[i] == 'x':\n",
    "                if x_zero == 0:\n",
    "                    left_x += 0\n",
    "                else:\n",
    "                    left_x += num * flag if num else flag\n",
    "                num = 0\n",
    "            elif equation[i] == '+':\n",
    "                left_stack.append(flag * num)\n",
    "                num, flag = 0, 1\n",
    "            elif equation[i] == '-':\n",
    "                left_stack.append(flag * num)\n",
    "                num, flag = 0 , -1\n",
    "            else:\n",
    "                #数字\n",
    "                num =10 * num + int(equation[i])\n",
    "                x_zero = num   \n",
    "        if num:\n",
    "            left_stack.append(num * flag)\n",
    "        num, flag = 0, 1\n",
    "        x_zero = -1\n",
    "        for j in range(index + 1, len(equation)):\n",
    "            if equation[j] == 'x':\n",
    "                if x_zero == 0:\n",
    "                    right_x += 0\n",
    "                else:\n",
    "                    right_x += num * flag if num else flag\n",
    "                num = 0\n",
    "            elif equation[j] == '+':\n",
    "                right_stack.append(flag * num)\n",
    "                num, flag = 0, 1\n",
    "            elif equation[j] == '-':\n",
    "                right_stack.append(flag * num)\n",
    "                num, flag = 0 , -1\n",
    "            else:\n",
    "                #数字\n",
    "                num =10 * num + int(equation[j])\n",
    "                x_zero = num\n",
    "        if num:\n",
    "            right_stack.append(num * flag)\n",
    "        sum_left = sum(left_stack)\n",
    "        sum_right = sum(right_stack)\n",
    "        # print(left_x, right_x)\n",
    "        print(left_stack, right_stack)\n",
    "        if left_x == right_x and sum_left == sum_right:\n",
    "            return \"Infinite solutions\"\n",
    "        elif left_x == right_x and sum_left != sum_right:\n",
    "            return \"No solution\"\n",
    "        elif left_x > right_x:\n",
    "            return \"x=\" + str((sum_right - sum_left) // (left_x - right_x))\n",
    "        else:\n",
    "            return \"x=\" + str((sum_left - sum_right) // (right_x - left_x))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        factor = val = 0\n",
    "        i, n, sign = 0, len(equation), 1  # 等式左边默认系数为正\n",
    "        while i < n:\n",
    "            if equation[i] == '=':\n",
    "                sign = -1\n",
    "                i += 1\n",
    "                continue\n",
    "\n",
    "            s = sign\n",
    "            if equation[i] == '+':  # 去掉前面的符号\n",
    "                i += 1\n",
    "            elif equation[i] == '-':\n",
    "                s = -s\n",
    "                i += 1\n",
    "\n",
    "            num, valid = 0, False\n",
    "            while i < n and equation[i].isdigit():\n",
    "                valid = True\n",
    "                num = num * 10 + int(equation[i])\n",
    "                i += 1\n",
    "\n",
    "            if i < n and equation[i] == 'x':  # 变量\n",
    "                factor += s * num if valid else s\n",
    "                i += 1\n",
    "            else:  # 数值\n",
    "                val += s * num\n",
    "\n",
    "        if factor == 0:\n",
    "            return \"No solution\" if val else \"Infinite solutions\"\n",
    "        return f\"x={-val // factor}\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "         # 1. 等式分为两边 等号左边计入left 右边计入right\n",
    "        # 2. 建立left_num, left_x, right_num, right_x \n",
    "        index = equation.index('=')\n",
    "        def get_res(start, end, flag):\n",
    "            val_sum, val_x, num = 0, 0, 0\n",
    "            x_zero = -1\n",
    "            for i in range(start, end):\n",
    "                if equation[i] == 'x':\n",
    "                    #x系数不为0\n",
    "                    if x_zero != 0:\n",
    "                        val_x += num * flag if num else flag\n",
    "                    num = 0\n",
    "                elif equation[i] == '+':\n",
    "                    val_sum += flag * num\n",
    "                    num, flag = 0, 1\n",
    "                elif equation[i] == '-':\n",
    "                    val_sum += flag * num\n",
    "                    num, flag = 0 , -1\n",
    "                else:\n",
    "                    num =10 * num + int(equation[i])\n",
    "                    x_zero = num # 考虑x系数是否为0\n",
    "            val_sum += flag * num\n",
    "            return val_sum, val_x\n",
    "        sum_left, left_x = get_res(0, index, 1)\n",
    "        sum_right, right_x = get_res(index + 1, len(equation), 1)\n",
    "\n",
    "        if left_x == right_x and sum_left == sum_right:\n",
    "            return \"Infinite solutions\"\n",
    "        elif left_x == right_x and sum_left != sum_right:\n",
    "            return \"No solution\"\n",
    "        else:\n",
    "            return f'x={str((sum_right - sum_left) // (left_x - right_x))}'\n",
    "    \n",
    "                \n",
    "\n",
    "        \n",
    "        \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        new_equation=equation.replace('-','+-')\n",
    "        equation=new_equation.split('=')\n",
    "        LHS=equation[0].split('+')\n",
    "        RHS=equation[1].split('+')\n",
    "        left_coeff=0\n",
    "        left_num=0\n",
    "        right_coeff=0\n",
    "        right_num=0\n",
    "        for i in range(len(LHS)):\n",
    "            if len(LHS[i])==0:\n",
    "                continue\n",
    "            if LHS[i][-1]=='x':\n",
    "                if len(LHS[i])==1:\n",
    "                    left_coeff+=1\n",
    "                elif len(LHS[i])==2:\n",
    "                    if LHS[i][0]=='-':\n",
    "                        left_coeff-=1\n",
    "                    else:\n",
    "                        left_coeff+=int(LHS[i][0])\n",
    "                else:\n",
    "                    left_coeff+=int(LHS[i][:-1])\n",
    "            else:\n",
    "                left_num+=int(LHS[i])\n",
    "        for i in range(len(RHS)):\n",
    "            if len(RHS[i])==0:\n",
    "                continue\n",
    "            if RHS[i][-1]=='x':\n",
    "                if len(RHS[i])==1:\n",
    "                    right_coeff+=1\n",
    "                elif len(RHS[i])==2:\n",
    "                    if RHS[i][0]=='-':\n",
    "                        right_coeff-=1\n",
    "                    else:\n",
    "                        right_coeff+=int(RHS[i][0])\n",
    "                else:\n",
    "                    right_coeff+=int(RHS[i][:-1])\n",
    "            else:\n",
    "                right_num+=int(RHS[i])\n",
    "        if (right_coeff-left_coeff)==0 and right_num-left_num!=0:\n",
    "            return 'No solution'\n",
    "        elif (right_coeff-left_coeff)==0 and right_num-left_num==0:\n",
    "            return 'Infinite solutions'\n",
    "        else:\n",
    "            return 'x='+str(-(right_num-left_num)//(right_coeff-left_coeff))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        equations = equation.split(\"=\")\n",
    "        left, right = equations[0], equations[1]\n",
    "\n",
    "        def parse(strs):\n",
    "            nums = 0\n",
    "            x_cnt = 0\n",
    "            pre, symbol = \"\", 1\n",
    "            for i in strs:\n",
    "                if i.isdigit():\n",
    "                    pre += i \n",
    "                elif i in [\"+\", \"-\"]:\n",
    "                    nums += int(pre)*symbol if pre != \"\" else 0\n",
    "                    if i == \"-\":\n",
    "                        symbol = -1\n",
    "                    else:\n",
    "                        symbol = 1\n",
    "                    pre = \"\"\n",
    "                elif i == \"x\":\n",
    "                    x_cnt += (int(pre) if pre != \"\" else 1) * symbol\n",
    "                    pre = \"\"\n",
    "            if pre != \"\":\n",
    "                nums += int(pre)*symbol\n",
    "            return nums, x_cnt\n",
    "        ln, lx = parse(left)\n",
    "        rn, rx = parse(right)\n",
    "        if lx-rx == 0:\n",
    "            if rn-ln == 0:\n",
    "                return \"Infinite solutions\"\n",
    "            return \"No solution\"\n",
    "        res = (rn-ln)//(lx-rx)\n",
    "        return \"x=\" + str(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        sign = 1\n",
    "        left = 1\n",
    "        i = 0\n",
    "        x_num = 0\n",
    "        const = 0\n",
    "        n = len(equation)\n",
    "        num = 1\n",
    "        while i < n:\n",
    "            if equation[i] == 'x':\n",
    "                x_num += left*sign*num\n",
    "                num = 1\n",
    "                sign=1\n",
    "            elif equation[i] == '=':\n",
    "                if left==-1:\n",
    "                    return 'No solution'\n",
    "                left = -1\n",
    "            elif equation[i] == '+':\n",
    "                sign = 1\n",
    "            elif equation[i] == '-':\n",
    "                sign = -1\n",
    "            else:\n",
    "                num = 0\n",
    "                while i < n and equation[i].isdigit():\n",
    "                    num = num*10+int(equation[i])\n",
    "                    i += 1\n",
    "                if i == n or equation[i] != 'x':\n",
    "                    const -= sign*left*num\n",
    "                    num = 1\n",
    "                    sign=1\n",
    "                i -= 1\n",
    "            i += 1\n",
    "        if x_num == 0 and const==0:\n",
    "            return 'Infinite solutions'\n",
    "        elif x_num==0 and const!=0 or const % x_num != 0:\n",
    "            return 'No solution'\n",
    "        else:\n",
    "            return f'x={const//x_num}'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        equation = equation.replace('-', '+-')\n",
    "        equation = equation.strip().split('=')\n",
    "        left = equation[0].split('+')\n",
    "        right = equation[1].split('+')\n",
    "        pre = C = 0\n",
    "        for i in left:\n",
    "            if not i: continue\n",
    "            if 'x' in i:\n",
    "                if len(i) == 1: pre += 1\n",
    "                elif len(i) == 2 and  '-' in i: pre -= 1\n",
    "                else: pre += int(i[:-1])\n",
    "            else:\n",
    "                C -= int(i)\n",
    "        for i in right:\n",
    "            if not i: continue\n",
    "            if 'x' in i:\n",
    "                if len(i) == 1: pre -= 1\n",
    "                elif len(i) == 2 and  '-' in i: pre += 1\n",
    "                else: pre -= int(i[:-1])\n",
    "            else:\n",
    "                C += int(i)\n",
    "        if pre == 0 and C == 0:\n",
    "            return 'Infinite solutions'\n",
    "        if pre == 0:\n",
    "            return 'No solution'\n",
    "        return 'x='+str(C//pre)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        leftStr = equation.split(\"=\")[0]\n",
    "        rightStr = equation.split(\"=\")[1]\n",
    "        leftACount = 0\n",
    "        leftNumCount = 0\n",
    "        rightACount = 0\n",
    "        rightNumCount = 0\n",
    "\n",
    "        def getCount(s:str):\n",
    "            acount = 0\n",
    "            numcount = 0\n",
    "            tmp = []\n",
    "            fuhao = 1\n",
    "            isA = False\n",
    "            for i in s:\n",
    "                if i==\"x\":\n",
    "                    if len(tmp)==0:\n",
    "                        acount+=fuhao\n",
    "                    else:\n",
    "                        acount+=int(\"\".join(tmp)) * fuhao\n",
    "                    tmp = []\n",
    "                    isA=True\n",
    "                elif i==\"+\":\n",
    "                    if isA:\n",
    "                        fuhao=1\n",
    "                        continue\n",
    "                    if tmp:\n",
    "                        numcount+=fuhao*int(\"\".join(tmp))\n",
    "                    tmp=[]\n",
    "                    fuhao=1\n",
    "                    isA=False\n",
    "                elif i ==\"-\":\n",
    "                    if isA:\n",
    "                        fuhao=-1\n",
    "                        continue\n",
    "                    if tmp:\n",
    "                        numcount+=fuhao*int(\"\".join(tmp))\n",
    "                    tmp=[]\n",
    "                    fuhao=-1\n",
    "                    isA=False\n",
    "                else:\n",
    "                    #数字\n",
    "                    tmp.append(i)\n",
    "                    isA=False\n",
    "            if tmp:\n",
    "                numcount+=fuhao*int(\"\".join(tmp))\n",
    "            return acount,numcount\n",
    "        leftACount,leftNumCount= getCount(leftStr)\n",
    "        rightACount,rightNumCount= getCount(rightStr)\n",
    "        if (leftACount-rightACount)==0:\n",
    "            if (rightNumCount-leftNumCount)!=0:\n",
    "                return \"No solution\"\n",
    "            return \"Infinite solutions\"\n",
    "        return f\"x={int((rightNumCount-leftNumCount)/(leftACount-rightACount))}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        # 1. 等式分为两边 等号左边计入left 右边计入right\n",
    "        # 2. 建立left_num, left_x, right_num, right_x \n",
    "        index = equation.index('=')\n",
    "        def get_res(start, end, flag):\n",
    "            val_sum, val_x, num = 0, 0, 0\n",
    "            x_zero = -1\n",
    "            for i in range(start, end):\n",
    "                if equation[i] == 'x':\n",
    "                    #x系数不为0\n",
    "                    if x_zero != 0:\n",
    "                        val_x += num * flag if num else flag\n",
    "                    num = 0\n",
    "                elif equation[i] == '+':\n",
    "                    val_sum += flag * num\n",
    "                    num, flag = 0, 1\n",
    "                elif equation[i] == '-':\n",
    "                    val_sum += flag * num\n",
    "                    num, flag = 0 , -1\n",
    "                else:\n",
    "                    num =10 * num + int(equation[i])\n",
    "                    x_zero = num # 考虑x系数是否为0\n",
    "            val_sum += flag * num\n",
    "            return val_sum, val_x\n",
    "        sum_left, left_x = get_res(0, index, 1)\n",
    "        sum_right, right_x = get_res(index + 1, len(equation), 1)\n",
    "\n",
    "        if left_x == right_x and sum_left == sum_right:\n",
    "            return \"Infinite solutions\"\n",
    "        elif left_x == right_x and sum_left != sum_right:\n",
    "            return \"No solution\"\n",
    "        else:\n",
    "            return f'x={str((sum_right - sum_left) // (left_x - right_x))}'\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        t1, t2 = equation.split('=')\n",
    "        if t2[0] not in '-+':\n",
    "            t2 = '+' + t2\n",
    "        t2 = list(t2)\n",
    "        for i in range(len(t2)):\n",
    "            if t2[i] == '+':\n",
    "                t2[i] = '-'\n",
    "            elif t2[i] == '-':\n",
    "                t2[i] = '+'\n",
    "\n",
    "        equation = t1 + ''.join(t2)\n",
    "        if equation[0] not in '-+':\n",
    "            equation = '+' + equation\n",
    "        x = 0\n",
    "        nums = 0\n",
    "\n",
    "        i = 0\n",
    "        n = len(equation)\n",
    "        while i < n:\n",
    "            k = 1 if equation[i] == '+' else -1\n",
    "            i += 1\n",
    "            if equation[i] == 'x':\n",
    "                x += 1 * k\n",
    "                i += 1 \n",
    "                continue\n",
    "\n",
    "            num = 0\n",
    "            while i < n and '0' <= equation[i] <= '9':\n",
    "                num = num * 10 + int(equation[i])\n",
    "                i += 1\n",
    "            if i < n and equation[i] == 'x':\n",
    "                x += num * k\n",
    "                i += 1\n",
    "            else:\n",
    "                nums += num * k\n",
    "\n",
    "        if x == 0 and nums == 0:\n",
    "            return \"Infinite solutions\"\n",
    "        if x == 0:\n",
    "            return \"No solution\"\n",
    "        if nums % x != 0:\n",
    "            return \"No solution\"\n",
    "        return \"x=%d\" % (-nums//x)\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        left,right = equation.split('=')\n",
    "\n",
    "        def help(ins):\n",
    "            length = len(ins)\n",
    "            xnum = 0\n",
    "            num = 0\n",
    "            add = True\n",
    "            i = 0\n",
    "            if ins[0]=='-':\n",
    "                add = False\n",
    "                i+=1\n",
    "            while i<length:\n",
    "\n",
    "                s = i\n",
    "                while i<length and ins[i]!='+' and ins[i]!='-':\n",
    "                    i+=1\n",
    "                sub = ins[s:i]\n",
    "                if sub[-1]=='x':\n",
    "                    if add:\n",
    "                        if len(sub)==1:\n",
    "                            xnum += 1\n",
    "                        else:\n",
    "                            xnum += int(sub[:len(sub)-1])\n",
    "                    else:\n",
    "                        if len(sub)==1:\n",
    "                            xnum -= 1\n",
    "                        else:\n",
    "                            xnum -= int(sub[:len(sub)-1])\n",
    "                else:\n",
    "                    if add:\n",
    "                        num += int(sub)\n",
    "                    else:\n",
    "                        num -= int(sub)\n",
    "                pass\n",
    "\n",
    "                if i<length:\n",
    "                    add = True if ins[i]=='+' else False\n",
    "                i+=1\n",
    "            return num, xnum\n",
    "\n",
    "        lnum, lx = help(left)\n",
    "        rnum, rx = help(right)\n",
    "        xnum = lx - rx\n",
    "        res = rnum - lnum\n",
    "        if xnum==0 and res!=0:\n",
    "            return \"No solution\"\n",
    "        elif xnum==0 and res==0:\n",
    "            return \"Infinite solutions\"\n",
    "        else:\n",
    "            if res % xnum !=0:\n",
    "                return \"No solution\"\n",
    "            else:\n",
    "                return \"x={}\".format(res//xnum)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        left,right = equation.split('=')\n",
    "\n",
    "        def help(ins):\n",
    "            length = len(ins)\n",
    "            xnum = 0\n",
    "            num = 0\n",
    "            add = True\n",
    "            i = 0\n",
    "            if ins[0]=='-':\n",
    "                add = False\n",
    "                i+=1\n",
    "            while i<length:\n",
    "                s = i\n",
    "                while i<length and ins[i]!='+' and ins[i]!='-':\n",
    "                    i+=1\n",
    "                sub = ins[s:i]\n",
    "                if sub[-1]=='x':\n",
    "                    if add:\n",
    "                        if len(sub)==1:\n",
    "                            xnum += 1\n",
    "                        else:\n",
    "                            xnum += int(sub[:len(sub)-1])\n",
    "                    else:\n",
    "                        if len(sub)==1:\n",
    "                            xnum -= 1\n",
    "                        else:\n",
    "                            xnum -= int(sub[:len(sub)-1])\n",
    "                else:\n",
    "                    if add:\n",
    "                        num += int(sub)\n",
    "                    else:\n",
    "                        num -= int(sub)\n",
    "                pass\n",
    "\n",
    "                if i<length:\n",
    "                    add = True if ins[i]=='+' else False\n",
    "                i+=1\n",
    "            return num, xnum\n",
    "\n",
    "        lnum, lx = help(left)\n",
    "        rnum, rx = help(right)\n",
    "        xnum = lx - rx\n",
    "        res = rnum - lnum\n",
    "        if xnum==0 and res!=0:\n",
    "            return \"No solution\"\n",
    "        elif xnum==0 and res==0:\n",
    "            return \"Infinite solutions\"\n",
    "        else:\n",
    "            if res % xnum !=0:\n",
    "                return \"No solution\"\n",
    "            else:\n",
    "                return \"x={}\".format(res//xnum)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        idx = equation.index('=')\n",
    "        s1 = equation[:idx]\n",
    "        s2 = equation[idx+1:]\n",
    "        def f(s):\n",
    "            res = ctx = 0\n",
    "            if s[0].isdigit() or s[0]=='x':\n",
    "                s = '+' +s\n",
    "            n = len(s )\n",
    "            left,right = 0,1\n",
    "            dic ={'-':-1,'+':1}\n",
    "            while right<n:\n",
    "                if s[right]  in {'+','-'}:\n",
    "                    tmps = s[left:right]\n",
    "                    print(tmps)\n",
    "                    if 'x' in tmps:\n",
    "                        if len(tmps) == 2:\n",
    "                            ctx += dic[tmps[0]]*1\n",
    "                        else:\n",
    "                            ctx += int(tmps[:len(tmps)-1])\n",
    "                    else:\n",
    "                        res += int(tmps)\n",
    "                    left = right\n",
    "                    # right += 1\n",
    "                elif right == n-1:\n",
    "                    print('1')\n",
    "                    tmps = s[left:right+1]\n",
    "                    print(tmps)\n",
    "                    if 'x' in tmps:\n",
    "                        if len(tmps) == 2:\n",
    "                            ctx += dic[tmps[0]]*1\n",
    "                        else:\n",
    "                            ctx += int(tmps[:len(tmps)-1])\n",
    "                    else:\n",
    "                        res += int(tmps)\n",
    "                    \n",
    "                right += 1\n",
    "            print(res,ctx)\n",
    "            return res,ctx\n",
    "        res1,ctx1 = f(s1)\n",
    "        res2,ctx2 = f(s2)\n",
    "        he = res1 - res2\n",
    "        ctx = ctx1-ctx2\n",
    "        print(res1,ctx1)\n",
    "        if he == 0 and ctx == 0:\n",
    "            return \"Infinite solutions\"\n",
    "        elif he !=0 and ctx == 0:\n",
    "            return \"No solution\" \n",
    "        else:\n",
    "            return \"x=\"+ str(-1*(he//ctx))\n",
    "                \n",
    "\n",
    "                        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def f(s,sign):\n",
    "        #     res = cnt = num = 0\n",
    "        #     sign2 = 1\n",
    "        #     n = len(s)\n",
    "        #     i = 0\n",
    "        #     while i<n:\n",
    "        #         if s[i] == '+':\n",
    "        #             sign2  = 1\n",
    "        #             i += 1\n",
    "        #             continue\n",
    "        #         if s[i] == '-':\n",
    "        #             sign2 = -1\n",
    "        #             i += 1\n",
    "        #             continue\n",
    "        #         while i<n and s[i].isdigit():\n",
    "        #             num = num*10 + int(s[i])\n",
    "        #             i += 1\n",
    "        #         if i<n and s[i] == 'x':\n",
    "        #             if i == 0 or (i>0 and not s[i-1].isdigit()):\n",
    "        #                 print(sign,sign2)\n",
    "        #                 cnt += sign*sign2\n",
    "        #             else:\n",
    "        #                 cnt += sign*sign2*num\n",
    "        #                 num = 0\n",
    "        #             sign2 = 1\n",
    "        #             i += 1\n",
    "        #         else:\n",
    "        #             res += sign*sign2*num\n",
    "        #             sign2 =1\n",
    "        #             num = 0\n",
    "        #     return res,cnt\n",
    "        res1,ctx1 = f(s1,1)\n",
    "        res2,ctx2 = f(s2,-1)\n",
    "        he = res1 + res2\n",
    "        ctx = ctx1+ctx2\n",
    "        print(res1,ctx1)\n",
    "        if he == 0 and ctx == 0:\n",
    "            return \"Infinite solutions\"\n",
    "        elif he !=0 and ctx == 0:\n",
    "            return \"No solution\" \n",
    "        else:\n",
    "            return \"x=\"+ str(-1*(he//ctx))\n",
    "                \n",
    " \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        def parse(s):\n",
    "            a,b=0,0#分别代表二者的系数\n",
    "            i,j=0,0\n",
    "            operand=''\n",
    "            while j<len(s):\n",
    "                while j<len(s) and s[j] not in '+-':\n",
    "                    j+=1\n",
    "                # tmp=s[i:j+1]\n",
    "                tmp=s[i:j]\n",
    "                # print(tmp)\n",
    "                # print('aa:',tmp[:-1])\n",
    "                if not tmp:continue\n",
    "                if tmp[-1]=='x':\n",
    "                    if tmp[:-1]=='-':a_tmp=-1\n",
    "                    else:a_tmp=int(tmp[:-1]) if tmp[:-1]!='' else 1\n",
    "                    if operand=='' or operand=='+':a+=a_tmp\n",
    "                    if operand=='-' :a-=a_tmp\n",
    "                else:\n",
    "                    if operand=='' or operand=='+':b+=int(tmp)\n",
    "                    if operand=='-':b-=int(tmp)\n",
    "                if j<len(s):operand=s[j]\n",
    "                i=j+1\n",
    "                j+=1\n",
    "            return a,b\n",
    "        part1=equation.strip().split('=')[0]\n",
    "        part2=equation.strip().split('=')[1]\n",
    "        if part1[0]in'+-':part1='0'+part1\n",
    "        if part2[0] in '+-':part2='0'+part2\n",
    "        a1,b1=parse(part1)\n",
    "        a2,b2=parse(part2)\n",
    "        print(a1,b1)\n",
    "        print(a2,b2)\n",
    "        if a1==a2 and b1==b2:return 'Infinite solutions'\n",
    "        if a1==a2 and b1!=b2:return 'No solution'\n",
    "        # return 'x='+str((b1-b2)/(a1-a2))\n",
    "        return 'x='+str(int((b1-b2)/(a2-a1)))\n",
    "            \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        # 1. 等式分为两边 等号左边计入left 右边计入right\n",
    "        # 2. 建立left_num, left_x, right_num, right_x \n",
    "        index = equation.index('=')\n",
    "        num, flag = 0, 1\n",
    "        left_stack, right_stack = [], []\n",
    "        left_x, right_x = 0, 0\n",
    "        x_zero = -1\n",
    "        for i in range(index):\n",
    "            if equation[i] == 'x':\n",
    "                if x_zero == 0:\n",
    "                    left_x = 0\n",
    "                else:\n",
    "                    left_x += num * flag if num else flag\n",
    "                num = 0\n",
    "            elif equation[i] == '+':\n",
    "                left_stack.append(flag * num)\n",
    "                num, flag = 0, 1\n",
    "            elif equation[i] == '-':\n",
    "                left_stack.append(flag * num)\n",
    "                num, flag = 0 , -1\n",
    "            else:\n",
    "                #数字\n",
    "                num =10 * num + int(equation[i])\n",
    "                x_zero = num   \n",
    "        if num:\n",
    "            left_stack.append(num * flag)\n",
    "        num, flag = 0, 1\n",
    "        x_zero = -1\n",
    "        for j in range(index + 1, len(equation)):\n",
    "            if equation[j] == 'x':\n",
    "                if x_zero == 0:\n",
    "                    right_x = 0\n",
    "                else:\n",
    "                    right_x += num * flag if num else flag\n",
    "                num = 0\n",
    "            elif equation[j] == '+':\n",
    "                right_stack.append(flag * num)\n",
    "                num, flag = 0, 1\n",
    "            elif equation[j] == '-':\n",
    "                right_stack.append(flag * num)\n",
    "                num, flag = 0 , -1\n",
    "            else:\n",
    "                #数字\n",
    "                num =10 * num + int(equation[j])\n",
    "                x_zero = num\n",
    "        if num:\n",
    "            right_stack.append(num * flag)\n",
    "        sum_left = sum(left_stack)\n",
    "        sum_right = sum(right_stack)\n",
    "        # print(left_x, right_x)\n",
    "        print(left_stack, right_stack)\n",
    "        if left_x == right_x and sum_left == sum_right:\n",
    "            return \"Infinite solutions\"\n",
    "        elif left_x == right_x and sum_left != sum_right:\n",
    "            return \"No solution\"\n",
    "        elif left_x > right_x:\n",
    "            return \"x=\" + str((sum_right - sum_left) // (left_x - right_x))\n",
    "        else:\n",
    "            return \"x=\" + str((sum_left - sum_right) // (right_x - left_x))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solveEquation(self, equation: str) -> str:\n",
    "        x=0\n",
    "        op=1\n",
    "        num=0\n",
    "\n",
    "        n=len(equation)\n",
    "        i=0\n",
    "        while i <= n-1:\n",
    "            if equation[i]=='+':\n",
    "                op=1\n",
    "                i+=1\n",
    "            elif equation[i]=='-':\n",
    "                op=-1\n",
    "                i+=1\n",
    "            elif equation[i]=='=':\n",
    "                op=1\n",
    "                x=-x\n",
    "                num=-num\n",
    "                i+=1\n",
    "            else:\n",
    "                j=i\n",
    "                while j<=n-1 and (equation[j]=='x' or '0'<=equation[j]<='9'):\n",
    "                    j+=1\n",
    "                if equation[j-1]=='x':\n",
    "                    if j-1>i:\n",
    "                        x = x+int(equation[i:j-1])*op\n",
    "                    else:\n",
    "                        x+=1*op\n",
    "                else:\n",
    "                    num+=int(equation[i:j])*op\n",
    "                \n",
    "                print(num)\n",
    "                print(x)\n",
    "                i=j\n",
    "\n",
    "        if x==0:\n",
    "            if num==0:\n",
    "                return \"Infinite solutions\"\n",
    "            else:\n",
    "                return \"No solution\"\n",
    "        else:\n",
    "            return \"x=\"+str(int(-num/x))\n",
    "\n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
